Masala #0666

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 13 %
3.2 (Baholar 5)
14

  

Gilos #3

Ikki do’st Hoshimjon va Orif ta’tilning keyingi n kuni davomida gilos terishmoqchi. Ammo do’stlar har doim ham o’zlari xohlaganchalik giloslarni tera olishmaydi va shunga qarab ularning kayfiyati o’zgarishi mumkin. Boshqacha qilib aytkanda do’stlar ii-kuni gilos tersa Hoshimjonni kayfiyatiga aia_i, Orifnikiga esa bib_i qo’shiladi (106ai,bi106)(-10^6 ≤ a_i, b_i ≤ 10^6).

Sizga ll va rr ko’rinishidagi qq ta so’rov beriladi. Agar do’stlar [l..r][l..r] oralig’idagi kunlarning har birida gilos teradigan bo’lsa, shu oraliqdagi do’stlarning umumiy xursandchilik koeffitsientini toping. Umumiy xursandchilik koeffitsienti quyidagicha hisoblanadi:

  • Dastlab, ll-kundan oldin, har bir bolaning kayfiyati 0 ga teng bo’ladi
  • ii - kuni (lir)(l ≤ i ≤ r) Hoshimjonning kayfiyati aia_i ga, Orifni kayfiyati bib_i ga o’zgaradi
  • ii - kun (lir)(l ≤ i ≤ r) uchun do’stlarning xursandchilik koeffitsienti Hoshimjon va Orifni shu kundagi kayfiyatlarini kattasiga teng bo’ladi
  • umumiy xursandchilik koeffitsienti barcha rl+1r - l + 1 kunlardagi xursandchilik koeffitsientlari yig’indisiga teng.

To’liqroq tushunish uchun quyida keltirilgan misolga qarang.


Kiruvchi ma'lumotlar:

Birinchi qatorda kunlar soni nn va so’rovlar soni qq kiritiladi (1n,q105)(1 ≤ n, q ≤ 10^5). Ikkinchi qatorda nn ta butun son a1,a2,...,ana_1, a_2, ..., a_n va 3-qatorda ham nn ta butun son b1,b2,...,bnb_1, b_2, ..., b_n kiritiladi (106ai,bi106)(-10^6 ≤ a_i, b_i ≤ 10^6).

Keyingi qq ta qatorda so’rovlar ll va rr butun sonlari ko’rinishida beriladi (1lrn)(1 ≤ l ≤ r ≤ n).

1-subtask(9 ball): n,q1000n, q ≤ 1000.
2-subtask(7 ball): ai=1,bi=0,n,q105a_i = 1, b_i = 0, n, q ≤ 10^5
3-subtask(13 ball): ai0,bi=0,n,q105a_i ≥ 0, b_i = 0, n, q ≤ 10^5
4-subtask(29 ball): bi=0,n,q105b_i = 0, n, q ≤ 10^5
5-subtask(42 ball): n,q105n, q ≤ 10^5


Chiquvchi ma'lumotlar:

Har bir so’rov uchun umumiy xursandchilik koeffitsientini chiqaring.


Misollar
# input.txt output.txt
1
6 7
3 -5 8 -10 3 7
-4 20 9 -100 105 20
1 6
1 5
2 4
3 3
3 6
2 5
4 5
120
70
42
9
55
76
-5
Izoh:

Birinchi misoldagi uchinchi so’rovni ko’raylik, do’stlar 2..4 kunlar oralig’ida gilos terishadi.

Dastlab, Hoshimjonning ham Orifning ham kayfiyati 0 ga teng.
2-kundan so’ng: Hoshimjonni kayfiyati = -5, Orifni kayfiyati = 20, xursandlik koeffitsienti 20 (chunki 20 > -5).
3-kundan so’ng: Hoshimjonni kayfiyati = -5 + 8 = 3, Orifni kayfiyati = 20 + 9 = 29, xursandlik koeffitsienti 29 (chunki 29 > 3).
4-kundan so’ng: Hoshimjonni kayfiyati = -5 + 8 + (-10) = -7, Orifni kayfiyati = 20 + 9 + (-100) = -71, xursandlik koeffitsienti -7 (chunki -7 > -100).
Shunday qilib, umumiy xursandlik koeffitsienti = 20 + 29 + (-7) = 42.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin