Masala B
Upsolve qarzi
Birinchi natijalardan keyin akademiyada bitta qoida sekin-asta odatga aylandi: contest tugashi bilan hammasi tugab qolmaydi. Yechilmay qolgan masala keyingi darsgacha "qarz" bo'lib turadi. Tahlilda eng avval eng eski qarz ochiladi, chunki eski xato qolib ketsa, yangi mavzu ham mustahkam bo'lmaydi.
Bir o'quvchining \(n\) kunlik yozuvi berilgan. Har bir kun bitta belgi bilan ifodalangan:
X- shu kuni bitta yangi xato paydo bo'ldi;U- shu kuni bitta upsolve qilindi;-- shu kuni yangi xato ham, upsolve ham bo'lmadi.
Har bir U belgisi hali yopilmagan xatolarning eng eskisini, ya'ni eng oldin paydo bo'lganini yopadi. Agar shu paytda yopilmagan xato bo'lmasa, bu U hech narsani o'zgartirmaydi.
Agar \(i\)-kunda paydo bo'lgan xato \(j\)-kunda yopilsa va \(j - i \le k\) bo'lsa, bu xato vaqtida yopilgan hisoblanadi. Umuman yopilmagan xato vaqtida yopilgan hisoblanmaydi.
Vaqtida yopilgan xatolar sonini toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le k \le n)\).
Ikkinchi qatorda uzunligi \(n\) ga teng \(s\) satri beriladi. Har bir belgi X, U yoki - bo'ladi.
Vaqtida yopilgan xatolar sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
7 3 X-XUUXU |
3 |
| 2 |
5 1 XX-UU |
0 |
| 3 |
6 2 XUXX-U |
1 |
Birinchi namunada \(1\)-kundagi xato \(4\)-kunda, \(3\)-kundagi xato \(5\)-kunda, \(6\)-kundagi xato \(7\)-kunda yopiladi. Farqlar mos ravishda \(3\), \(2\) va \(1\); uchalasi ham \(k=3\) dan oshmaydi.
Ikkinchi namunada \(1\)-kundagi xato \(4\)-kunda, \(2\)-kundagi xato \(5\)-kunda yopiladi. Ikkala farq ham \(3\) ga teng, bu \(k=1\) dan katta.
Uchinchi namunada \(1\)-kundagi xato \(2\)-kunda yopiladi (farq \(1 \le 2\)). \(3\)-kundagi xato \(6\)-kunda yopiladi (farq \(3 > 2\)), \(4\)-kundagi xato esa umuman yopilmaydi. Demak, javob \(1\).
Telegram kanalimizga obuna bo'ling