RACE - Đường đua kì lạ
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

Việc đua xe diễn ra thường xuyên trên hành tinh Alpha. Nhưng đua xe ở đây rất kì lạ so với ở Trái Đất, có N chiếc xe trên một đường đua thẳng dài. Mỗi xe di chuyển với tốc độ 1 m/s. Xe thứ di chỉ di chuyển từ ai đến bi, bắt đầu từ giây thứ 0 tại điểm ai. Chúng di chuyển từ ai đến bi, sau đó từ bi trở về ai, rồi từ ai đến bi và cứ lặp đi lặp lại như vậy.

Natalia muốn loại một số chiếc xe ra khỏi đường đua bằng bom. Vì vậy cô ta có M câu hỏi, câu hỏi thứ i là: tại thời điểm ti, trong đoạn từ xi đến yi có bao nhiêu chiếc xe.. Hãy giúp cô ấy trả lời những câu hỏi đó nhé.

Dữ liệu nhập: Dòng đầu tiên chứa 2 số nguyên N, M - số luợng xe trêm đường đua và số lượng câu hỏi. (1 ≤ N, M ≤ 1000). N dòng tiếp theo, mỗi dòng chứa 2 số nguyên ai, bi - phạm vi di chuyển của xe thứ i (0 ≤ ai, bi ≤ 109). M dòng cuối cùng, mỗi dòng chứa 3 số nguyên xi, yi và ti - tọa độ đoạn đường và thời gian của câu hỏi.

Dữ liệu xuất: Gồm M dòng, mỗi dòng chứa một số nguyên duy nhất là câu trả lời của câu hỏi thứ i trong M câu hỏi.

Ví dụ

  • input
    5 5
    0 1
    0 2
    2 3
    3 5
    4 5
    0 5 0
    0 1 2
    0 2 1
    2 5 2
    2 5 3
    output
    5
    1
    2
    4
    3

   

Back to Top