CSES - Movie Festival Queries | Lễ hội phim ảnh
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Trong một lễ hội phim ảnh, \(n\) bộ phim sẽ được chiếu. Bạn biết được thời điểm bắt đầu và thời điểm kết thức của từng bộ phim.
Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: nếu bạn đến và rời lễ hội vào những thời điểm cụ thể, số lượng bộ phim mà bạn có thể xem nhiều nhất là bao nhiêu?
Bạn có thể xem hai bộ phim nếu bộ thứ nhất kết thúc trước hoặc ngay lúc bộ thứ hai bắt đầu. Bạn có thể xem bộ phim thứ nhất bắt đầu ngay khi bạn đến và rời đi ngay lúc bộ phim cuối cùng kết thúc.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) lần lượt là số lượng bộ phim và số lượng truy vấn.
- \(n\) dòng tiếp theo mô tả các bộ phim. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) là thời điểm bắt đầu và kết thúc của một bộ.
- \(q\) dòng cuối cùng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) là thời điểm đến và rời đi của bạn.
Output
- In ra số lượng bộ phim nhiều nhất cho từng truy vấn.
Constraints
- \(1 \le n, q \le 2 \times 10^5\)
- \(1 \le a < b \le 10^6\)
Example
Sample input
4 3
2 5
6 10
4 7
9 10
5 9
2 10
7 10
Sample output
0
2
1
Bình luận
CSES - Movie Festival Queries | Truy vấn lễ hội phim ảnh
Trong một lễ hội phim ảnh, \(n\) bộ phim sẽ được chiếu. Bạn biết thời gian bắt đầu và kết thúc của mỗi bộ phim.
Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: nếu bạn đến và rời lễ hội vào những thời điểm cụ thể, số bộ phim tối đa bạn có thể xem là bao nhiêu?
Bạn có thể xem hai bộ phim nếu bộ phim thứ nhất kết thúc trước hoặc ngay lúc bộ thứ hai bắt đầu. Bạn có thể bắt đầu xem phim ngay lúc bạn đến và rời đi ngay lúc bộ phim cuối cùng bạn xem kết thúc.
Input
Output
Test 1
Input
Output