Convoluted Intervals

Đ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

Cho $N$ đoạn trên trục số, đoạn thứ $i$ có hai đầu mút $a_{i}$ và $b_{i}$ (với $0 \leq a_{i} \leq b_{i} \leq M$ ).

Bessie và Elsie mỗi người chọn một đoạn (có thể trùng nhau). Giả sử Bessie chọn đoạn $i$ , Elsie chọn đoạn $j$ . Họ thắng nếu tồn tại số nguyên $k$ thỏa mãn $a_{i} + a_{j} \leq k \leq b_{i} + b_{j}$ .

Với mỗi $k$ từ $0$ đến $2 M$ , đếm số cặp có thứ tự $(i, j)$ thắng.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $M$ .
$N$ dòng tiếp: Mỗi dòng gồm hai số nguyên $a_{i}$ và $b_{i}$ .

Dữ liệu ra

In $2 M + 1$ dòng, dòng thứ $k$ (bắt đầu từ $0$ ) là số cặp thắng ứng với giá trị $k$ đó.

Ràng buộc

$1 \leq N \leq 2 \times 10^{5}$ .
$1 \leq M \leq 5000$ .
$0 \leq a_{i} \leq b_{i} \leq M$ .

Ví dụ

Input	Output	Giải thích
2 5 1 3 2 5	0 0 1 3 4 4 4 3 3 1 1	Với $k = 3$ : ba cặp $(1, 1), (1, 2), (2, 1)$ thắng.

Bình luận

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