Truy vấn Liên hoan Phim

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ bộ phim, bộ phim thứ $i$ chiếu từ thời điểm $a_{i}$ đến $b_{i}$ . Bạn có thể xem hai bộ phim liên tiếp nếu bộ phim trước kết thúc không muộn hơn lúc bộ phim sau bắt đầu.

Với mỗi truy vấn cho biết thời gian bạn đến $x$ và thời gian bạn rời $y$ , hãy tìm số bộ phim tối đa bạn có thể xem. Bạn chỉ xem được bộ phim nào bắt đầu không sớm hơn lúc bạn đến và kết thúc không muộn hơn lúc bạn rời.

Dữ liệu vào

Dòng 1: Hai số nguyên $n$ và $q$ ( $1 \leq n, q \leq 2 \times 10^{5}$ ).
$n$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a_{i}$ và $b_{i}$ ( $1 \leq a_{i} < b_{i} \leq 10^{6}$ ).
$q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $x$ và $y$ ( $1 \leq x < y \leq 10^{6}$ ).

Dữ liệu ra

Với mỗi truy vấn, in ra số bộ phim tối đa có thể xem trên một dòng.

Ràng buộc

$1 \leq n, q \leq 2 \times 10^{5}$
$1 \leq a_{i} < b_{i} \leq 10^{6}$
$1 \leq x < y \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
4 3 2 5 6 10 4 7 9 10 5 9 2 10 7 10	0 2 1	Truy vấn [5,9]: không có phim nào thỏa mãn ( $s \geq 5$ và $e \leq 9$ ). Truy vấn [2,10]: xem phim (2,5) rồi (6,10), được 2 phim. Truy vấn [7,10]: chỉ xem được (9,10), được 1 phim.
3 2 1 3 2 5 4 7 1 7 3 7	2 1	Truy vấn [1,7]: xem (1,3) rồi (4,7), được 2 phim. Truy vấn [3,7]: chỉ xem (4,7), được 1 phim (phim (1,3) bắt đầu trước thời điểm 3).

Bình luận

Không có bình luận tại thời điểm này.