A. Qiziqarli massiv

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Uzungli 2*M ga teng bo'lgan massiv qiziqarli massiv deyiladi qachonki dastlabki M ta elementining yig'indisi SUM dan oshmasa hamda shu holat oxirgi M ta element uchun ham o'rinli bo'lsa.

Sizga N va SUM  mos ravishda N ta elementdan iborat A massiv va SUM qiziqarli massivni aniqlash uchun beriladi.

Sizning vazifangiz massivning har bir elementi maximum nechi uzunlikdagi qiziqarli massivning birinchi elementi bo'la olishini aniqlash 

Kiruvchi ma'lumotlar:

Birinchi qatorda  \(N\) va SUM \((1 ≤ N ≤ 10^5, 1 ≤ SUM ≤ 10^9)\) mos ravishda massiv elementlari soni va qiziqarli massivni aniqlashda kerak bo'ladigan yig'indi

Keyingi N ta qatorda massiv elementlari butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.

Chiquvchi ma'lumotlar:

N ta qatorda massivning har bir elementi maximum nechi uzunlikdagi qiziqarli massivning birinchi elementi bo`lishini aniqlang!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 10000
1
1
1
1
1
 
4
4
2
2
0
2 
5 9
1
1
10
1
9
 
2
0
0
2
0
3 
8 3
1
1
1
1
1
1
1
1
 
6
6
6
4
4
2
2
0

B. Sanash (EASY)

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Tasavvur qiling \(N\) ta o'quvchi stol atrofida o'tirishibdi, ular o'yin o'ynashmoqchi bo'lishdi.

O'yin sharti quyidagicha ular 1 dan boshlab sanashni davom ettirishadi va har juft sanoqdagi o'quvchi o'yindan chetlashtiriladi va stol atrofidan ham ketadi.

Sizning vazifangiz stol atrofida nechta o'quvchi borligini bilgan holda o'yin bo'yicha o'quvchilarni o'yinda chiqib ketish tartibini chiqaring

Kiruvchi ma'lumotlar:

Yagona qatorda \(N (1 ≤ N ≤ 2 * 10^5)\) butun soni, stol atrofidagi o'quvchilar soni

Chiquvchi ma'lumotlar:

Yagona qatorda probel bilan ajratgan holda masala yechimi sifatida N ta butun sonni chiqaring 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1
 
1
2 
2
 
2 1
3 
3
 
2 1 3

C. Sanash (HARD)

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Tasavvur qiling \(N\) ta o'quvchi stol atrofida o'tirishibdi, ular o'yin o'ynashmoqchi bo'lishdi.

O'yin sharti quyidagicha ular 1 dan boshlab sanashni davom ettirishadi va har \(K\)-sanoqdagi o'quvchi o'yindan chetlashtiriladi va stol atrofidan ham ketadi.

Sizning vazifangiz stol atrofida nechta o'quvchi borligini bilgan holda o'yin bo'yicha o'quvchilarni o'yinda chiqib ketish tartibini chiqaring

Kiruvchi ma'lumotlar:

Yagona qatorda \(N\) va \(K (1 ≤  N ≤ 2 * 10^5, 0 ≤  K ≤ 10^9)\) butun sonlari, mos ravishda stol atrofidagi o'quvchilar soni va har bir chiqib ketishi kerak bo'lgan sanoq miqdori

Chiquvchi ma'lumotlar:

Yagona qatorda probel bilan ajratgan holda masala yechimi sifatida \(N\) ta butun sonni chiqaring 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 0
 
1
2 
1 1
 
1
3 
1 2
 
1

D. Prefix yig'indi (so'rovli) (EASY)

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov berilad, so'rovlar quyidagicha:

  • 1 \(K\) \(X\) turdagi so'rovda \(K\)-o'rindagi massiv elementini \(X\) ga almashtirish
  • 2 \(L\) \(R\) turdagi so'rovda berilgan oraliqdagi eng katta prefix summani topish
Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 10^2)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 10^2\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ L ≤ R, K ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1
1
2 1 1
 
1

E. Prefix yig'indi (so'rovli) (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov berilad, so'rovlar quyidagicha:

  • 1 \(K\) \(X\) turdagi so'rovda \(K\)-o'rindagi massiv elementini \(X\) ga almashtirish
  • 2 \(L\) \(R\) turdagi so'rovda berilgan oraliqdagi eng katta prefix summani topish
Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ L ≤ R, K ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1
1
2 1 1
 
1

F. Kadane (so'rovli) (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov beriladi, har bir so'rovda massivning \(K\)-elementi qiymati \(X\) ga o'zgaradi.

Sizning vazifangiz o'zgargan massivdan eng katta yig'indiga ega qism massiv topish (bu turdagi masalani eng tez yechib beruvchi algoritm nomi: Kadane) !

Siz qism massiv summasini chop eting

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.
Keyingi qatorda \(N\) ta butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.
Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ K ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir so'rovdan keyin massivda eng katta Kadane qiymatini chiqarish!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1
1
1 10
 
10

G. Kadane (so'rovli) (EASY)

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov beriladi, har bir so'rovda massivning \(K\)-elementi qiymati \(X\) ga o'zgaradi.

Sizning vazifangiz o'zgargan massivdan eng katta yig'indiga ega qism massiv topish (bu turdagi masalani eng tez yechib beruvchi algoritm nomi: Kadane) !

Siz qism massiv summasini chop eting

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 10)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.
Keyingi qatorda \(N\) ta butun \(A[i] (-10^9 ≤ A[i] ≤ 10^9)\) sonlari.
Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 10\)
\(-10^9 ≤ A[i], X ≤ 10^9\)
\(1 ≤ K ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir so'rovdan keyin massivda eng katta Kadane qiymatini chiqarish!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1 1
1
1 10
 
10

H. Persistent Segment Tree (EASY)

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Ushbu masalada massivlar soni ko'payib boradi.

Sizga dastlab N va Q mos ravishda N ta elementdan iborat A massiv uzunligi va shu massiv ustida amalga oshiriladigan Q ta so'rovlar soni beriladi, quyidagi so'rovlarning 3-turida massiv yana bittaga ko'payadi.

Sizning vazifangiz quyidagi so'rovlarga javob beruvchi ma'lumotlari tuzilmasini tuzish albatta o'z o'rnida har bir 2-turdagi so'rovga javob qaytarish:

  • 1 ID X Y bu so'rovda siz ID-massivning X-elementini Y ga o'zgartirishing
  • 2 ID L R bu so'rovda siz ID-massivning [L, R] oraliqdagi elementlari yig'indisini chiqarish
  • 3 ID bu so'rovda siz ID-massivda yana bir nusxa oling shunda sizning massivlaringiz soni yana bittaga ko'payadi

 

Kiruvchi ma'lumotlar:

 Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 10^2)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (1 ≤ A[i] ≤ 10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 10^2\)
\(1 ≤ A[i], Y ≤ 10^9\)
\(1 ≤ L ≤ R, X ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 15
1 2 3
3 1
3 2
3 3
3 4
1 1 1 5
1 2 1 50
1 3 1 500
1 4 1 5000
1 5 1 50000
2 1 1 3
2 2 1 3
2 3 1 3
2 4 1 3
2 5 1 3
3 5
 
10
55
505
5005
50005

I. Persistent Segment Tree (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Ushbu masalada massivlar soni ko'payib boradi.

Sizga dastlab N va Q mos ravishda N ta elementdan iborat A massiv uzunligi va shu massiv ustida amalga oshiriladigan Q ta so'rovlar soni beriladi, quyidagi so'rovlarning 3-turida massiv yana bittaga ko'payadi.

Sizning vazifangiz quyidagi so'rovlarga javob beruvchi ma'lumotlari tuzilmasini tuzish albatta o'z o'rnida har bir 2-turdagi so'rovga javob qaytarish:

  • 1 ID X Y bu so'rovda siz ID-massivning X-elementini Y ga o'zgartirishing
  • 2 ID L R bu so'rovda siz ID-massivning [L, R] oraliqdagi elementlari yig'indisini chiqarish
  • 3 ID bu so'rovda siz ID-massivda yana bir nusxa oling shunda sizning massivlaringiz soni yana bittaga ko'payadi
Kiruvchi ma'lumotlar:

 Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (1 ≤ A[i] ≤ 10^9)\) sonlari.

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:
\(1 ≤ N, Q ≤ 2 * 10^5\)
\(1 ≤ A[i], Y ≤ 10^9\)
\(1 ≤ L ≤ R, X ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda 2-turdagi so'rovlar uchun mos javobni chiqaring

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 15
1 2 3
3 1
3 2
3 3
3 4
1 1 1 5
1 2 1 50
1 3 1 500
1 4 1 5000
1 5 1 50000
2 1 1 3
2 2 1 3
2 3 1 3
2 4 1 3
2 5 1 3
3 5
 
10
55
505
5005
50005

J. Oraliqga qo'shish va o'zgartirish (EASY)

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov berilgan, so'rovlar quyidagicha:

  1. \(L \space R \space X\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlarga \(X\) sonini qo'shish
  2. \(L \space R \space X\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlar qiymatini \(X\) soniga tenglashtirish
  3. \(L \space R\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlar yig'indisini chiqarish
Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 10^2)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (1 ≤ A[i] ≤ 10^6)\) sonlari

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:

\(1 ≤ N, Q ≤ 10^2\)
\(1 ≤ A[i], X ≤ 10^6\)
\(1 ≤ L ≤ R ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir 3-turdagi so'rov uchun berilgan \([L, R]\) oraliqdagi massiv elementlari yig'indisini chiqaring!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 3
1 2 3
1 1 2 3
2 2 3 1
3 1 3
 
6

K. Oraliqga qo'shish va o'zgartirish (HARD)

Xotira: 512 MB, Vaqt: 1000 ms
Masala

Sizga \(N\) ta elementdan iborat \(A\) massiv va \(Q\) ta so'rov berilgan, so'rovlar quyidagicha:

  1. \(L \space R \space X\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlarga \(X\) sonini qo'shish
  2. \(L \space R \space X\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlar qiymatini \(X\) soniga tenglashtirish
  3. \(L \space R\) turdagi so'rovda \([L, R]\) oraliqdagi barcha elementlar yig'indisini chiqarish
Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q (1 ≤ N, Q ≤ 2 * 10^5)\) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

Keyingi qatorda \(N\) ta butun \(A[i] (1 ≤ A[i] ≤ 10^6)\) sonlari

Keyingi \(Q\) ta qatorda so'rovlar beriladi. 

Chegaralar:

\(1 ≤ N, Q ≤ 2 * 10^5\)
\(1 ≤ A[i], X ≤ 10^6\)
\(1 ≤ L ≤ R ≤ N\)

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir 3-turdagi so'rov uchun berilgan \([L, R]\) oraliqdagi massiv elementlari yig'indisini chiqaring!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3 3
1 2 3
1 1 2 3
2 2 3 1
3 1 3
 
6
Kitob yaratilingan sana: 28-Apr-24 05:08