Masala #0665
Gilos #2
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 \(i\)-kuni gilos tersa Hoshimjonni kayfiyatiga \(a_i\), Orifnikiga esa \(b_i\) qo’shiladi \((-10^6 ≤ a_i, b_i ≤ 10^6)\).
Sizga \(l\) va \(r\) ko’rinishidagi \(q\) ta so’rov beriladi. Agar do’stlar \([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, \(l\)-kundan oldin, har bir bolaning kayfiyati 0 ga teng bo’ladi
- \(i\) - kuni \((l ≤ i ≤ r)\) Hoshimjonning kayfiyati \(a_i\) ga, Orifni kayfiyati \(b_i\) ga o’zgaradi
- \(i\) - kun \((l ≤ i ≤ r)\) uchun do’stlarning xursandchilik koeffitsienti Hoshimjon va Orifni shu kundagi kayfiyatlarini kattasiga teng bo’ladi
- umumiy xursandchilik koeffitsienti barcha \(r - l + 1\) kunlardagi xursandchilik koeffitsientlari yig’indisiga teng.
To’liqroq tushunish uchun quyida keltirilgan misolga qarang.
Birinchi qatorda kunlar soni \(n\) va so’rovlar soni \(q\) kiritiladi \((1 ≤ n, q ≤ 10^5)\). Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, ..., a_n\) va 3-qatorda ham \(n\) ta butun son \(b_1, b_2, ..., b_n\) kiritiladi \((-10^6 ≤ a_i, b_i ≤ 10^6)\).
Keyingi \(q\) ta qatorda so’rovlar \(l\) va \(r\) butun sonlari ko’rinishida beriladi \((1 ≤ l ≤ r ≤ n)\).
1-subtask(9 ball): \(n, q ≤ 1000\).
2-subtask(7 ball): \(a_i = 1, b_i = 0, n, q ≤ 10^5\)
3-subtask(13 ball): \(a_i ≥ 0, b_i = 0, n, q ≤ 10^5\)
4-subtask(29 ball): \(b_i = 0, n, q ≤ 10^5\)
5-subtask(42 ball): \(n, q ≤ 10^5\)
Har bir so’rov uchun umumiy xursandchilik koeffitsientini chiqaring.
# | 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 |
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.