C. Paxta dalasi
900 ball
Fermer xo‘jaligining paxta dalasi N qator va M ustunli katakchalarga bo‘lingan. Qatorlar yuqoridan pastga 1 dan N gacha, ustunlar chapdan o‘ngga 1 dan M gacha raqamlangan. (i, j) katakdan a[i][j] kilogramm paxta terildi.
Xo‘jalik rahbari Q ta so‘rov beradi. Har bir so‘rovda dalaning to‘g‘ri to‘rtburchak qismi — chap yuqori burchagi (x₁, y₁) va o‘ng pastki burchagi (x₂, y₂) — beriladi. Shu qismdan jami necha kilogramm paxta terilganini tez hisoblang.
Kirish ma’lumotlari
Birinchi qatorda N va M. Keyingi N ta qatorning har birida M tadan butun son — a[i][j]. So‘ng Q soni, keyingi Q ta qatorning har birida to‘rtta son: x₁ y₁ x₂ y₂.
Chiqish ma’lumotlari
Har bir so‘rov uchun alohida qatorda — o‘sha qismdagi jami paxta.
Cheklovlar
- 1 ≤ N, M ≤ 500
- 0 ≤ a[i][j] ≤ 10⁹
- 1 ≤ Q ≤ 10⁵
- 1 ≤ x₁ ≤ x₂ ≤ N, 1 ≤ y₁ ≤ y₂ ≤ M
- Yig‘indi 2,5 · 10¹⁴ gacha: C++ da
long longishlating.
Misollar
3 4 1 2 3 4 5 6 7 8 9 10 11 12 3 1 1 3 4 2 2 3 3 1 4 3 4
78 34 24
Tushuntirish
Misolda: butun dala — 78 kg; (2, 2)–(3, 3) qismi — 34 kg (rasmda); oxirgi ustun — 4 + 8 + 12 = 24 kg.