| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P161SUMJ - ROUND 1J - Đoạn thẳng và điểm |
Cho n đoạn thẳng, mỗi đoạn thẳng được biểu diễn bởi 1 cặp số (l, r) với ý nghĩa đoạn thẳng có 2 đầu mút ở vị trí l và r trên trục Ox.
Nhiệm vụ của bạn là trả lời các truy vấn, mỗi truy vấn sẽ gồm tập hợp các điểm cho trước và đếm số đoạn thẳng mà có chứa ít nhất một điểm trong tập điểm đó. Một điểm ở vị trí p gọi là bị chứa bởi đoạn thẳng (l, r) nếu l <= p <= r.
Input
Dòng đầu tiên gồm 2 số nguyên n và m (1 <= n, m <= 3.10^5)
n dòng tiếp theo, mỗi dòng gồm 2 số nguyên (l, r) đại diện cho một đoạn thẳng (1 <= l, r <= 10^6)
m dòng tiếp, mỗi dòng số đầu tiên là c đại diện cho số điểm trong tập hợp, c số tiếp theo là các điểm của truy vấn, tọa độ các điểm là số nguyên không âm, và không quá 10^6.
Số lượng các điểm trong tất cả các truy vấn không quá 3.10^5.
Output
m dòng, mỗi dòng là kết quả của các truy vấn theo thứ tự xuất hiện trong input.
Example
Input:3 1
Output:
439010 864662
377278 743032
771051 955458
1 568232
2
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-07 |
| Thời gian chạy: | 0.5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
