Giám Sát

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ con bò ở trại, mỗi con là trại viên hoặc huấn luyện viên. Một tập con không rỗng được chọn đi dã ngoại, mỗi bò $i$ được đặt tại vị trí $p_{i}$ trên trục số (các vị trí tăng ngặt).

Tập con là "tốt" nếu mọi trại viên được chọn đều có một huấn luyện viên được chọn cách không quá $D$ đơn vị về bên trái (bao gồm cả vị trí bằng nhau).

Đếm số tập con tốt, modulo $10^{9} + 7$ .

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $D$
$N$ dòng tiếp theo: Hai số nguyên $p_{i}$ và $o_{i}$ ( $o_{i} = 1$ nếu là huấn luyện viên, $o_{i} = 0$ nếu là trại viên)

Dữ liệu ra

Một số nguyên — số tập con tốt modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 10^{6}$
$0 \leq p_{i} \leq 10^{9}$
$0 \leq D \leq 10^{9}$
Các $p_{i}$ tăng ngặt

Ví dụ

Input	Output	Giải thích
6 1 3 1 4 0 6 1 7 1 9 0 10 0	11	Hai trại viên cuối không thể tham gia (không có HLV trong khoảng $D = 1$ ). Các tập con tốt không chứa bò 5, 6 trừ khi có HLV phù hợp.
20 24 3 0 14 0 17 1 20 0 21 0 22 1 28 0 30 0 32 0 33 1 38 0 40 0 52 0 58 0 73 0 75 0 77 1 81 1 84 1 97 0	13094	Xem lời giải chi tiết.

Bình luận

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