Стайня
Обмеження: 7 сек., 512 МіБ
Як ви вже знаєте, у Зеника з Марічкою є \(n\) жеребців, пронумерованих від \(1\) до \(n\), яких вони тримають у стайні.
Наявність коней у стайні можна задати рядком \(t\) довжини \(n\), що складається із символів
0
і 1
. \(t_i=\,\)1
, якщо кінь з номером
\(i\) зараз у стайні, та \(t_i=\,\)0
, якщо він на
пасовищі.
Задано рядок \(s\), що описує стайню зранку.
Протягом дня Марічка веде коней на пасовище та повертає до стайні.
За одну дію Марічка може:
Відвести зі стайні на пасовище всіх жеребців з номерами від \(1\) до \(i\). Деякі з них можуть уже бути на пасовищі.
Привести з пасовища до стайні всіх жеребців з номерами від \(1\) до \(i\). Деякі з них можуть уже бути в стайні.
Час від часу протягом дня Зеник питає в Марічки, чи є в стайні \(i\)-ий кінь?
Вам задано \(q\) запитів:
1 i 0
— Марічка відводить на пасовище коней з номерами від \(1\) до \(i\).1 i 1
— Марічка приводить до стайні коней з номерами від \(1\) до \(i\).2 i
— Зеник питає в Марічки, чи \(i\)-ий кінь у стайні.
Марічка й так уже втомилася від своєї роботи, а ще Зеник зі своїми питаннями. Допоможіть Марічці відповісти на них.
Вхідні дані
У першому рядку задано два цілі числа \(n\) та \(q\) — кількість коней у стайні і кількість запитів відповідно.
У другому рядку задано рядок \(s\).
У наступних \(q\) рядках задано запити в описаному вище форматі.
Вихідні дані
На кожне запитання Зеника виведіть відповідь в окремому рядку —
1
, якщо в стайні є кінь, або 0
, якщо нема.
Обмеження
\(1 \le n \le 5 \cdot 10^5\),
\(1 \le q \le 3 \cdot 10^5\),
рядок \(s\) складається із символів
0
і 1
,
Зеник поставить принаймні одне питання Марічці.
Оцінювання складається з таких блоків:
1 бал за приклад з умови,
19 балів: Марічка не приводить коней з пасовища до стайні,
12 балів: \(n \le 1000, q \le 1000\),
30 балів: \(q \le 2 \cdot 10^4\),
38 балів: без додаткових обмежень.
Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 8 11011 1 4 1 2 3 1 5 0 2 3 2 5 1 4 1 2 3 2 5 | 1 0 0 1 0 |
Примітки
Розглянемо приклад.
Марічка приводить коней з номерами від \(1\) до \(4\) з пасовища до стайні. Рядок стає
11111
.Зеник запитує, чи є в стайні кінь з номером \(3\). Відповідь:
1
(у стайні є кінь).Марічка відводить коней з номерами від \(1\) до \(5\) на пасовище. Рядок стає
00000
.Зеник запитує, чи є в стайні кінь з номером \(3\). Відповідь:
0
(у стайні немає коня).Зеник запитує, чи є в стайні кінь з номером \(5\). Відповідь:
0
(у стайні немає коня).Марічка приводить коней з номерами від \(1\) до \(4\) з пасовища до стайні. Рядок стає
11110
.Зеник запитує, чи є в стайні кінь з номером \(3\). Відповідь:
1
(у стайні є конь).Зеник запитує, чи є в стайні кінь з номером \(5\). Відповідь:
0
(у стайні немає коня).
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|