CBOX - Hộp đựng tiền
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: nxphuc

An có N hộp đựng tiền được đánh số từ 1 đến N, ban đầu chúng đều rỗng. Mỗi ngày cậu ta chọn ra 1 cặp (L, R) và bỏ vào mỗi hộp trong đoạn có chỉ số từ L đến R 1 đồng tiền. Cậu ta thực hiện như vậy trong M ngày.

Sau M ngày, An muốn biết có bao nhiêu hộp đựng tiền có ít nhất X đồng tiền trong đó và cậu ta có Q câu hỏi như vậy.

Dữ liệu nhập:

 - Dòng đầu tiên chứa một số nguyên dương N – số hộp tiền.

 - Dòng thứ hai chứa một số nguyên dương M – số ngày mà An thực hiện

 - M dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương L và R

 - Dòng thứ M + 3 chứa một số nguyên Q – số lượng truy vấn

 - Q dòng cuối, mỗi dòng chứa một số nguyên dương X

Dữ liệu xuất: Gồm Q dòng, mỗi dòng chứa một số nguyên dương duy nhất là kết quả của truy vấn tương ứng.

Ràng buộc:

 - 1  N, M, Q  106

 - 1  L  R  N

 - 1  X  N

Ví dụ

  • input
    7
    4
    1 3
    2 5
    1 2
    5 6
    4
    1
    7
    4
    2
    output
    6
    0
    0
    4
Back to Top