DAYNGO2 - Dãy ngoặc 2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Khái niệm dãy ngoặc đúng được định nghĩa dưới dạng đệ quy như sau:

1. () là dãy ngoặc đúng

2. C là dãy ngoặc đúng nếu C = (A) hay C = AB với A, B là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()

Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(

Cho trước một dãy ngoặc bất kỳ gồm n dấu ngoặc được đánh số từ 1 đến n. Có m câu hỏi, mỗi câu gồm hai số nguyên 1 ≤ p ≤ r ≤ n, yêu cầu xác định xem dãy ngoặc con từ vị trí p đến vị trí r có phải là dãy ngoặc đúng hay không. Hãy cho biết kết quả của m câu hỏi trên.

Dữ liệu nhập:

- Dòng đầu tiên là hai số nguyên n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 105)

- Dòng thứ hai là dãy ngoặc ban đầu gồm n dấu ngoặc '(' hay ')'.

- Trong m dòng tiếp theo, tại dòng thứ i là hai số pi và ri của câu hỏi thứ i tương ứng, hai số cách nhau một khoảng trắng. (1 ≤ pi ≤ ri ≤ n).

Dữ liệu xuất:

- Gồm m dòng ứng với m câu hỏi, nếu dãy ngoặc con tương ứng là dãy ngoặc đúng, in ra YES, nếu dãy ngoặc con tương ứng là không phải dãy ngoặc đúng, in ra NO.

Ví dụ

  • input
    8 5
    (((())))
    1 4
    3 6
    4 8
    4 5
    2 7
    output
    NO
    YES
    NO
    YES
    YES
Back to Top