Masala #0176
Uchuvchi
Shaharda 1 dan \(n\) gacha raqamlangan \(n\) ta bino bor, \(i\)-bino balandligi \(h_i\). Uchuvchini \(m\) ta samolyoti bor, \(i\)- samolyot \(a_i\) balandlikkacha ko’tarila oladi.
Uchuvchi parvozini qaysidir \(s\) shaharda boshlab, \(t\) shaharda tugatadi, bunda \(s ≤ t\) bo’lishi lozim. Ya’ni u faqat o’ng tomonga ucha oladi. Uchuvchi samolyot ko’tarila oladigan balandlikdan baland binoga bora olmaydi.
Sizning vazifangiz har bir samolyot uchun, necha xil parvoz uyushtirish mumkinligini topishdan iborat
Birinchi qatorda mos ravishda binolar soni va samolyotlar sonini bildiruvchi \(n\) va \(m\) sonlari beriladi \((1 ≤ n, m ≤ 10^5)\). Ikkinchi qatorda \(n\) ta butun son \(h_1, h_2, \space\dots\space, h_n\) beriladi. Uchinchi qatorda esa \(m\) ta butun son, \(a_1, a_2, \space\dots\space, a_m\) beriladi \((1 ≤ h_i, a_i ≤ 10^6)\).
Har bir samolyot uchun turli xil parvozlar sonini toping.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
6 3 1 3 2 4 1 2 2 3 4 |
5 9 21 |
Birinchi samolyot bilan uchuvchi quyidagicha parvozlarni amalga oshirishi mumkin: (1, 1), (3, 3), (5, 5), (5, 6), (6, 6).
Telegram kanalimizga obuna bo'ling