Đếm đoạn thẳng bao phủ cặp điểm

General
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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$
Draft saved