Masala #1156
Robolandiya poyezdlari
Robolandiya mamlakatida \(N\) ta shahar mavjud. Har bir shahar ketma-ket joylashgan va har biri tartib bilan raqamlangan. Bundan tashqari, ushbu shaharlar orasida qatnovchi \(M\) ta poyezd bor. \(i-\)poyezd \(L_i\) - \(R_i\) shaharlari orasida qatnaydi \((1 \le L_i \le R_i \le N)\).
Robolandiya qiroli ushbu poyezdlarga qiziqib qoldi va endi u vazirlaridan so'ramoqda: ″\(p_i\) va \(q_i\) shaharlari orasida qatnovchi nechta poyezd bor?″.
Sizning vazifangiz quyidagi shartni qanoatlantiruvchi poyezdlar sonini topishdir.
\(p_i \le L_j \le R_j \le q_i\).
Kirish faylining birinchi qatorida uchta butun son - N, M, Q - shaharlar, poyezdlar va so'rovlar soni \((1 \le N \le 500, 1 \le M , Q \le 2*10^6)\).
Keyingi M ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(L_i\) va \(R_i\) mavjud.
Keyingi Q ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(p_i\) va \(q_i\) mavjud.
Chiqish faylining Q ta qatorida, har bir so'rov uchun ushbu oraliqda harakatlanuvchi poyezdlar sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 3 1 1 1 1 2 2 2 1 2 |
3 |
| 2 |
5 10 5 3 4 1 4 1 2 1 1 2 5 2 5 1 2 1 3 3 5 3 4 1 2 1 1 5 5 1 5 2 4 |
3 1 0 10 2 |
Telegram kanalimizga obuna bo'ling