DRAW1402H - Định và Uyên (bản khó)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: CaiWinDao

Sau khi nhận được yêu cầu trợ giúp từ đàn em dungde99, anh dvh312 đã bĩu môi khinh thường độ khó của bài toán và tiến hành "chế biến" nó thành một phiên bản hóc búa hơn như sau:

    Cho hệ trục tọa độ Oxy và Q truy vấn, mỗi truy vấn có dạng “A x y” hoặc “Q”:

    1. Truy vấn “A x y” yêu cầu chấm thêm điểm (x, y) lên mặt phẳng toạ độ
    2. Truy vấn "Q" yêu cầu in ra độ dài lớn nhất của dãy chỉ số i1, i2,..., ik sao cho i1 < i2 < ... < ikxi1 < xi2 < ... < xik cũng như yi1 < yi2 < ... < yik.
    Bạn hãy thử sức trước bài toán lý thú của anh dvh312 nhé! 
 
Định dạng input:
- Dòng đầu chứa số nguyên dương Q.
- Dòng thứ i trong Q dòng sau có dạng "A xi yi" nếu truy vấn thứ i thuộc loại thứ nhất hoặc "Q" nếu trong trường hợp ngược lại.
 
Định dạng output:
- Với mỗi truy vấn "Q," in ra một số nguyên là kết quả của truy vấn đó. Mỗi câu trả lời được in trên một dòng riêng biệt theo thứ tự xuất hiện trong input. Nếu gặp phải truy vấn "Q" khi chưa có điểm nào được chấm lên mặt phẳng tọa độ thì in ra 0.
 
Ràng buộc:
- Q 2*105.
- 1 ≤ xi, yi 1000 với mọi i.
 

Ví dụ

  • input
    7
    A 1 4
    A 2 2
    Q
    A 2 1
    A 1 1
    A 3 4
    Q
    output
    1
    2
Back to Top