Bedao Regular Contest 14 - BRACKET
Xem dạng PDF
Gửi bài giải
Điểm:
0,60 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
có dãy ngoặc độ dài ~n~ và ~q~ truy vấn dạng ~(l, r)~. Với mỗi truy vấn, hãy giúp tìm hai chỉ số ~L, R~ thỏa mãn:
Dãy con tạo bởi đoạn ~[L, R]~ tạo thành dãy ngoặc đúng
~L \le l~ và ~r \le R~
~R - L~ nhỏ nhất có thể
Input
Dòng đầu tiên chứa ~2~ số nguyên dương ~n, q~ (~n, q \leq 2 \cdot 10^5~) — độ dài dãy ngoặc và số truy vấn của bài toán.
Dòng thứ hai chứa dãy ngoặc độ dài ~n~. ~q~ dòng tiếp theo, dòng thứ ~i~ gồm ~2~ số ~l, r~ (~1 \leq l \leq r \leq n~) thể hiện truy vấn thứ ~i~.
Output
Gồm ~q~ dòng. Dòng thứ ~i~ trả lời cho truy vấn thứ ~i~ chứa ~2~ chỉ số ~L, R~ biểu diễn dãy tìm được nếu tồn tại đáp án, ngược lại in ~-1~.
Scoring
Subtask ~1~ (~50~ điểm): ~0 < n \le 1000~.
Subtask ~2~ (~50~ điểm): không có ràng buộc gì thêm.
Sample Input 1
10 10
))(()()()(
3 7
4 4
6 9
5 7
1 6
1 7
3 8
5 8
7 9
7 10
Sample Output 1
-1
4 5
6 9
4 7
-1
-1
-1
4 9
6 9
-1
Bình luận
https://ideone.com/6IHREG