Masala B
A + B multiple
Shohjahon va Arslonbek informatika darsida massivlar mavzusini birga o'rganishdi. Ular massiv ichidan sonni qidirish, uni tartibga keltirish kabi algoritmlarni o'zlashtirishdi. Mavzuni to'liq tushunganligini tekshirish uchun Shavkat ustoz ularga quyidagicha topshiriq berdi:
- Avvalo doskaga, bir-biridan farqli bo'lgan \(N\) ta butun sonni ketma-ket yozdi.
- Keyin bolalardan birma-bir quyidagicha savol so'radi: \(a\) va \(b\) butun sonlari berilgan bo'lsa. \(a + b\) ning qiymati doskada yozilgan ketma-ketlikning qaysi o'rnida ekanligini topish zarur.
Bolalarga bu ishni tezlikda topishiga yordam bering.
Kirish faylining birinchi qatorida ikkita butun son \(N\) va \(Q\) - ketma-ketlik uzunligi va so'rovlar soni beriladi.
Keyingi qatorda \(N\) ta butun son - Shavkat ustoz doskaga ketma-ketlik elementlari - \( c_i\) kiritiladi.
Keyingi \(Q\) ta qatorning har birida ikkitadan butun son - \(a_j\) va \(b_j\) sonlari probel bilan ajratilgan holatda kiritiladi.
Chegaralar:
\(1 \le N, Q \le 2 \times 10^5\)
\(-10^9 \le c_i, a_j, b_j \le 10^9\)
\(c\) massivdagi barcha elementlar bir biridan farqli ekanligi kafolatlanadi.
Subtasklar:
- Subtask 1. \(Q = 1\) (14 ball)
- Subtask 2. \(N \times Q \le 2 \times 10^5\) (17 ball)
- Subtask 3. \(0 \le c_i, a_j, b_j \le 10^6\) (30 ball)
- Subtask 4. Qo'shimcha chegaralarsiz. (39 ball)
Har bir so'rov uchun, alohida qatorda agar ketma-ketlikda ushbu qiymat mavjud bo'lsa uning pozitsiyasini, aks holda \(-1\) ni chop eting. Bunda pozitsiyalar 0 dan boshlanadi.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 6 -2 7 0 4 10 1 3 -1 -1 10 0 6 3 4 3 5 -3 |
3 0 4 -1 1 -1 |
Massiv \(c\): \([−2,7,0,4,10]\). Indekslar 0 dan boshlanadi.
- \(a=1,\ b=3\). \(a+b=4\). \(4\) massivda \(3\)-o‘rinda turibdi. Javob \(3\).
- \(a=-1,\ b=-1\). \(a+b=-2\). \(-2\) massivda \(0\)-o‘rinda turibdi. Javob \(0\).
- \(a=10,\ b=0\). \(a+b=10\). \(10\) massivda \(4\)-o‘rinda turibdi. Javob \(4\).
- \(a=6,\ b=3\). \(a+b=9\). \(9\) massivda mavjud emas. Shuning uchun javob \(-1\).
- \(a=4,\ b=3\). \(a+b=7\). \(7\) massivda \(1\)-o‘rinda turibdi. Javob \(1\).
- \(a=5,\ b=-3\). \(a+b=2\). \(-2\) massivda mavjud emas. Shuning uchun javob \(-1\).
Telegram kanalimizga obuna bo'ling