Đếm đoạn thẳng bao phủ cặp điểm
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Trên trục số cho $N$ đoạn thẳng $[L_i, R_i]$ ($L_i \le R_i$) và $M$ truy vấn. Mỗi truy vấn gồm hai số nguyên $X_j, Y_j$ ($X_j \le Y_j$). Hãy đếm xem có bao nhiêu đoạn thẳng trong $N$ đoạn đã cho bao phủ hoàn toàn đoạn $[X_j, Y_j]$, tức là thỏa mãn $L_i \le X_j$ và $Y_j \le R_i$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $M$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $X_j, Y_j$.
Dữ liệu ra
Gồm $M$ dòng, dòng thứ $j$ là kết quả cho truy vấn thứ $j$.
Ví dụ
| Input | Output |
|---|---|
| 4 3 1 5 2 4 3 8 1 10 2 4 3 6 5 5 |
3 2 3 |
Giới hạn
- $1 \le N, M \le 10^5$
- $1 \le L_i \le R_i \le 10^9$
- $1 \le X_j \le Y_j \le 10^9$
Community Discussion