Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Dany jest ciąg nawiasów ( i
). Zadanie polegać będzie na weryfikacji poprawności
nawiasowania dla wielu podsłów zadanego ciągu nawiasowania.
Napisz program, który wczyta ciąg nawiasów oraz zapytania o poprawność nawiasowania wybranych podsłów ciągu, wyznaczy dla każdego zapytania czy nawiasowanie jest poprawne i wypisze wyniki na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i
określające kolejno: długość ciągu nawiasów i liczbę zapytań. W drugim
wierszu znajduje się ciąg długości N złożony ze znaków ( i
).
W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb naturalnych Ai, Bi, oddzielonych pojedynczym odstępem. Określają one zapytanie o poprawność zadanego spójnego podciągu nawiasowania od Ai-tego znaku do Bi-tego znaku.
Wyjście
Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć
odpowiedź dla i-tego
zapytania. Odpowiedź dla każdego zapytania to jedno słowo
TAK, jeśli nawiasowanie jest poprawne lub NIE
w przeciwnym przypadku.
Ograniczenia
1 ≤ N ≤ 1 000 000, 1 ≤ Q ≤ 1 000 000.
Przykład
| Input | Output | |
|
|