A. f(x)*f(x)*x
Xotira: 512 MB, Vaqt: 4000 ms\(x\) sonining chiroyliligi \(g(x)\) bilan belgilanadi. U quyidagicha hisoblanadi:
\[g(x) = f(x) * f(x) * x\]Bu yerda \(f(x)\) - \(x\)sonda ishlatilgan turli raqamlar soni. Masalan: \(f(1220) = 3\);\(f(93) = 2\); \(f(9876543210) = 10\). Sizga \(L, R\) hamda \(MOD\) beriladi. Sizning vazifangiz \([L, R]\) oralig'ida joylashgan barcha natural sonlarning chiroyliligini yig'indisini topish. Boshqa so'zlar bilan aytganda, quyidagini hisoblang:
\[\sum_{x=l}^{r} g(x)\]Natija juda ham katta bo'lishi mumkin. Shu sabab javobning \(MOD\) ga bo'lgandagi qoldig'ini chop eting.
Kirish faylida \(T (1 \le T \le 500)\) - testlar soni kiritiladi.
Keyingi \(T\) ta qatorning har birida 3 ta natural sonlar - \(L, R (1 \le L \le R \le 10^{200})\) va \(MOD(2 \leq MOD \leq 500)\)sonlari kiritiladi.
- Subtask #1: \(T \le 10\); \(L = 1\); \(R \le 10^6\) (8 ball)
- Subtask #2: \(T \le 1\); \(R-L \le 10^6\) (12 ball)
- Subtask #3: \(T \le 1\); \(R \le 10^{18}\) (20 ball)
- Subtask #4: \(T \le 2\); \(R \le 10^{50}; MOD \leq 200\) (30 ball)
- Subtask #5: Hamma testlar uchun \(MOD = const\), ya'ni \(MOD_i = MOD_j \ (1 \le i, j \le T)\) (30 ball)
Har bir test uchun alohida qatorda natijani chop eting.
1-namunaviy test, 1-subtaskning 1-testiga to'g'ri keladi.
2-namunaviy test, 2-subtaskning 1-testiga to'g'ri keladi.
3-namunaviy test, 3-subtaskning 1-testiga to'g'ri keladi.
4-namunaviy test, 5-subtaskning 1-testiga to'g'ri keladi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 1 5 300 1 10 300 1 150 300 |
15 85 32 |
| 2 |
1 1234567790 1234567890 13 |
4 |
| 3 |
1 1234 123412341234 315 |
234 |
| 4 |
3 1 100 349 100 1000 349 1000 100000000000000000000 349 |
83 147 231 |
B. Mehmonlar tashrifi
Xotira: 256 MB, Vaqt: 2000 msRobolandiya mamlakati nihoyat tinimsiz janglardan so'ng ozodlikka erishdi. Endilikdagi maqsad mamlakatdagi barcha shaharlar orasida yo'l qurish. Mamlakatda \(N\) ta shahar hamda hozircha bu shaharlarni bog’lovchi yo’llar umuman mavjud emas. Jami \(M\) ta ikki tomonlama yo’llar qurish rejalashtirilgan. \(u\) va \(v\) shaharni bog’lovchi yo’l \((u, v)\) ko'rinishida ifodalanadi. Yo’l qurilish rejasi tayyor va unga ko’ra birinchi bo’lib \((u_1, v_1)\), ikkinchi bo’lib \((u_2, v_2)\)… oxirgi bo’lib \((u_M, v_M)\) yo’li quriladi. Istalgan bir yo’lni qurish uchun 1 kun vaqt kerak.
\(S\) to’plami mavjud va bu to’lam hozircha bo’sh.
Bu mamlakatga mehmonlar kelmoqchi. Mehmonlar rejasiga ko’ra ular \(S\) to’plamdagi istalgan bir shahardan boshlab, qurilgan yo’llardan yurgan shu to’plamdagi barcha shaharlarni ko’rib chiqishmoqchi. Bunda ular sayohati davomida ba’zi shaharlarni bir necha marta aylanishsa yoki to'plamda bo'lmagan shaharlarga kirishsa ham mayli. Ularning butun sayohati vaqt olmaydi deb tasavur qiling!
Ikki xil turdagi \(Q\) ta so’rovlar beriladi.
\(+\ X\) so’rovi. \(S\) to’plamiga \(X\) - shaharni qo’shish (to’plamda oldin \(X\) shahri yo’qligi kafolatlanadi)
\(-\ X\) so’rovi. \(S\) to’plamdan \(X\) - shaharni o’chirish (to’plamda \(X\) shahri borligi kafolatlanadi)
Har safar S to’plamga o’zgartirish kiritilganidan so’ng, agar yo’l qurilishi bugun boshlansa, kamida necha kundan so’ng ushbu sayohatchilar mamlakatga tashrif buyurishlari mumkinligini ayting.
Kirish faylida \(N\) va \(M\) sonlari beriladi \((1 \le N \le 10^5, 1 \le M \le 5 * 10^5)\).
Keyingi \(M\) ta qatorning har birida ikkitadan butun son - \(u_i\) va \(v_i\) kiritiladi.\((1 \le i \le M, 1 \le u_i, v_i \le N, u_i \neq v_i)\). Barcha yo'llar qurilib bo'lganidan so'ng, hamma shaharlar bog'langan bo'lishi kafolatlanadi.
Keyingi qatorda bitta butun son - \(Q(1 \leq Q \leq 4*10^5)\) so'rovlar soni kiritiladi.
Keyingi \(Q\) ta qatorda so'rovlar kiritiladi.
Subtask #1: \(M = N-1\); \(X_i = i\); \(Y_i = i+1\) (4 ball)
Subtask #2: \(N \le 100\); \(M, Q \leq 400\) (7 ball)
Subtask #3: \(N \le 3000\); \(Q \leq 6000\) (12 ball)
Subtask #4: \(N, Q \le 4*10^4\), har qanday holatda \(|S| \le 2\) (27 ball)
Subtask #5: \(Q \le 500\) (15 ball)
Subtask #6: Qo'shimcha cheklovlarsiz (35 ball)
Chiqish faylida har bir so'rov uchun alohida qatorda minimum necha kun kutish kerakligini chop eting.
(\(S\) bo’sh bo’lsa \(-1\) chiqaring, \(S\) 1 ta elementdan tashkil topgan bo’lsa \(0\) chiqaring)
1-namunaviy test, 1-subtaskning 1-testiga to'g'ri keladi.
2-namunaviy test, 4-subtaskning 1-testiga to'g'ri keladi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 4 1 2 2 3 3 4 4 5 5 + 1 + 2 + 3 + 5 - 3 |
0 1 2 4 4 |
| 2 |
5 7 2 3 1 5 5 2 2 1 1 3 3 4 5 3 8 + 1 + 2 - 2 + 5 - 1 + 4 - 5 - 4 |
0 3 0 2 0 6 0 -1 |
C. Qat'iy o'suvchi oraliqlar
Xotira: 256 MB, Vaqt: 1500 msUzunligi \(N\) ga teng bo'lgan\(A\) massivi berilgan. \([L, R]\) oraliqqa yoqimtoy oraliq deyiladi, agarda shu oraliqdan tashkil qilgan massiv qat'iy o'suvchi hisoblansa. Boshqa so'zlar bilan aytganda \(A_l < A_{l+1} < ... < A_r\) sharti bajarilishi lozim.
Bundan tashqari \(Q\) ta so'rov mavjud, har bir so'rov uchun \(x\) va \(y\) sonlari kiritiladi. Bundan so'ng massivdagi \(x\)-element \(y\) soniga o'zgaritirladi. Ya'ni \(A_x \leftarrow y\) o'rnatiladi.
\(N\) va \(Q\) kiritiladi \((1 \le N, Q \le 2 * 10^5)\).
Keyingi qatorda N ta butun son - A massiv elementlari kiritiladi \((1 \le A_i \le 10^9)\).
Keyingi Q ta qatorning har birida ikkitadan butun son x va y kiritiladi.
- Subtask #1: \(N, Q \le 80\) (10 ball)
- Subtask #2: \(N, Q \le 500\) (20 ball)
- Subtask #3: \(N, Q \le 5000\) (30 ball)
- Subtask #4: Qo'shimcha cheklovlarsiz (40 ball)
Keyingi \(Q\) ta qatorda har bir so'rovdan so'ng massivdagi qat'iy o'suvchi oraliqlar sonini chop eting.
1-test 1-subtaskning 1-testiga to'g'ri keladi.
2-test 1-subtaskning 2-testiga to'g'ri keladi.
4-subtaskning 1-test: \(A_i = i\), \(Q = 1\), \(x_1 = 1\),\(y_1 = 1\)
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 100 10 2 2 3 1 2 1000 |
3 4 |
| 2 |
8 13 10 14 4 20 6 9 16 5 2 3 2 10 1 5 3 15 2 5 |
13 13 15 15 13 |