Kiểm Tra Luồng Dữ Liệu Bệnh Nhân Chợ Rẫy

Mô tả

Tại Bệnh viện Chợ Rẫy, dữ liệu bệnh nhân được truyền qua nhiều nút xử lý (nhận hồ sơ, mã hóa, lưu trữ). Mỗi lượt truyền được ghi nhận bằng một mã giao dịch: nếu dữ liệu đi vào một nút, ta nhận lệnh có dạng I x (với x là mã nút); nếu dữ liệu đi ra khỏi một nút, ta nhận lệnh R x.

Vì lý do bảo mật, dữ liệu chỉ được phép rời khỏi nút gần nhất mà nó bước vào trước (nguyên lý Last-In-First-Out). Nhiệm vụ của bạn là kiểm tra xem chuỗi lệnh giao dịch đã cho có hoàn toàn hợp lệ hay không, tức là:

• Lệnh R x chỉ xảy ra khi nút gần nhất được dữ liệu bước vào đúng là nút x.
• Sau khi xử lý hết mọi lệnh, không còn dữ liệu mắc kẹt ở bất kỳ nút nào.

Đầu vào

• Dòng đầu tiên chứa số nguyên n — số lượng lệnh giao dịch.
• n dòng tiếp theo, mỗi dòng có dạng I x hoặc R x, trong đó x là mã nút (số nguyên dương).

Đầu ra

• In ra 1 nếu toàn bộ luồng dữ liệu hợp lệ, ngược lại in ra 0.

Ràng buộc

• 1 ≤ n ≤ 200000
• 1 ≤ x ≤ 10^9

Ví dụ

Ví dụ 1:

Đầu vào:

6 I 5 I 10 R 10 I 20 R 20 R 5

Đầu ra:

1

Giải thích: Dữ liệu vào nút 5, rồi vào nút 10. Lệnh R 10 khớp với nút trên đỉnh (10) nên hợp lệ. Tiếp theo vào nút 20, ra nút 20 — khớp. Cuối cùng R 5 khớp với nút 5 còn sót lại. Hết lệnh, ngăn xếp rỗng nên kết quả là 1.

Ví dụ 2:

Đầu vào:

4 I 1 I 2 R 1 R 2

Đầu ra:

0

Giải thích: Sau khi vào nút 1 rồi nút 2, đỉnh ngăn xếp là 2, nhưng lệnh thứ ba lại yêu cầu R 1 — không khớp với đỉnh nên luồng bị lỗi, kết quả 0.