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  NN va SUM (1≤N≤105,1≤SUM≤109)(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](−109 ≤A[i] ≤109)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 NN 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∗105)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 NN 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 KK-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 NN va K(1≤ N≤2∗105, 0≤ K≤109)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 NN 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 NN ta elementdan iborat AA massiv va QQ ta so'rov berilad, so'rovlar quyidagicha:

  • 1 KK XX turdagi so'rovda KK-o'rindagi massiv elementini XX ga almashtirish
  • 2 LL RR turdagi so'rovda berilgan oraliqdagi eng katta prefix summani topish
Kiruvchi ma'lumotlar:

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

Keyingi qatorda NN ta butun A[i](−109 ≤A[i] ≤109)A[i] (-10^9 ≤ A[i] ≤ 10^9) sonlari.

Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:
1≤N,Q≤1021 ≤ N, Q ≤ 10^2
−109 ≤A[i],X≤109-10^9 ≤ A[i], X ≤ 10^9
1≤L≤R,K ≤N1 ≤ 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 NN ta elementdan iborat AA massiv va QQ ta so'rov berilad, so'rovlar quyidagicha:

  • 1 KK XX turdagi so'rovda KK-o'rindagi massiv elementini XX ga almashtirish
  • 2 LL RR turdagi so'rovda berilgan oraliqdagi eng katta prefix summani topish
Kiruvchi ma'lumotlar:

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

Keyingi qatorda NN ta butun A[i](−109 ≤A[i] ≤109)A[i] (-10^9 ≤ A[i] ≤ 10^9) sonlari.

Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:
1≤N,Q≤2∗1051 ≤ N, Q ≤ 2 * 10^5
−109 ≤A[i],X≤109-10^9 ≤ A[i], X ≤ 10^9
1≤L≤R,K ≤N1 ≤ 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 NN ta elementdan iborat AA massiv va QQ ta so'rov beriladi, har bir so'rovda massivning KK-elementi qiymati XX 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 NN va Q(1≤N,Q≤2∗105)Q (1 ≤ N, Q ≤ 2 * 10^5) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.
Keyingi qatorda NN ta butun A[i](−109 ≤A[i] ≤109)A[i] (-10^9 ≤ A[i] ≤ 10^9) sonlari.
Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:
1≤N,Q≤2∗1051 ≤ N, Q ≤ 2 * 10^5
−109 ≤A[i],X≤109-10^9 ≤ A[i], X ≤ 10^9
1≤K ≤N1 ≤ 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 NN ta elementdan iborat AA massiv va QQ ta so'rov beriladi, har bir so'rovda massivning KK-elementi qiymati XX 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 NN va Q(1≤N,Q≤10)Q (1 ≤ N, Q ≤ 10) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.
Keyingi qatorda NN ta butun A[i](−109 ≤A[i] ≤109)A[i] (-10^9 ≤ A[i] ≤ 10^9) sonlari.
Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:
1≤N,Q≤101 ≤ N, Q ≤ 10
−109 ≤A[i],X≤109-10^9 ≤ A[i], X ≤ 10^9
1≤K ≤N1 ≤ 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 NN va Q(1≤N,Q≤102)Q (1 ≤ N, Q ≤ 10^2) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

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

Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:
1≤N,Q≤1021 ≤ N, Q ≤ 10^2
1 ≤A[i],Y≤1091 ≤ A[i], Y ≤ 10^9
1≤L≤R,X ≤N1 ≤ 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 NN va Q(1≤N,Q≤2∗105)Q (1 ≤ N, Q ≤ 2 * 10^5) butun sonlari mos ravishda massiv elementlari soni va so'rovlar soni.

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

Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:
1≤N,Q≤2∗1051 ≤ N, Q ≤ 2 * 10^5
1 ≤A[i],Y≤1091 ≤ A[i], Y ≤ 10^9
1≤L≤R,X ≤N1 ≤ 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 NN ta elementdan iborat AA massiv va QQ ta so'rov berilgan, so'rovlar quyidagicha:

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

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

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

Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:

1≤N,Q≤1021 ≤ N, Q ≤ 10^2
1 ≤A[i],X≤1061 ≤ A[i], X ≤ 10^6
1≤L≤R≤N1 ≤ L ≤ R ≤ N

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir 3-turdagi so'rov uchun berilgan [L,R][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 NN ta elementdan iborat AA massiv va QQ ta so'rov berilgan, so'rovlar quyidagicha:

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

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

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

Keyingi QQ ta qatorda so'rovlar beriladi. 

Chegaralar:

1≤N,Q≤2∗1051 ≤ N, Q ≤ 2 * 10^5
1 ≤A[i],X≤1061 ≤ A[i], X ≤ 10^6
1≤L≤R≤N1 ≤ L ≤ R ≤ N

Chiquvchi ma'lumotlar:

Chiquvchi faylda har bir 3-turdagi so'rov uchun berilgan [L,R][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: 07-Apr-25 07:26