PIGGY - Heo Đất
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ớ: 512 megabyte
Đăng bởi: Biển

Tí có N heo đất đượ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 con heo đất 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.

Yêu cầu: Sau M ngày, Tí muốn biết có bao nhiêu con heo đất 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: Vào từ file văn bản PIGGY.INP gồm 

  • Dòng đầu tiên chứa một số nguyên dương N – số con heo đất.
  • Dòng thứ hai chứa một số nguyên dương M – số ngày mà Tí 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 câu hỏi
  • 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 từng câu hỏi tương ứng.

Ràng buộc:

  • 1 ≤ N, M, Q ≤ 106
  • 1 ≤ L ≤ R ≤ N
  • 1 ≤ X ≤ M

Ví dụ

PIGGY.INP

 

PIGGY.OUT

7

4

 1 3

 2 5

 1 2

 5 6

4

1

7

4

2

6

0

0

4

 

Back to Top