JOI 2025 - Collision
Xem PDFBitaro sống bên một hồ lớn hình tròn có chu vi \(L\). Nhà của Bitaro nằm tại một điểm trên bờ hồ. Gọi điểm cách nhà Bitaro một quãng đường \(x\) theo chiều kim đồng hồ dọc bờ hồ (\(0 \le x < L\)) là điểm \(x\). Hiện tại, một cuộc thi marathon quanh hồ đang được lên kế hoạch.
Bitaro nghe nói cuộc thi sẽ diễn ra như sau:
- Ban tổ chức chuẩn bị các số đeo từ \(0\) đến \(L-1\), mỗi số có đúng một chiếc. Mỗi người tham gia đeo một trong các số này. Người đeo số \(l\) (\(0 \le l \le L-1\)) xuất phát tại điểm \(l\).
- Trong \(T\) giây kể từ khi cuộc thi bắt đầu, mỗi người di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc của mình. Thời điểm sau khi cuộc thi bắt đầu được \(t\) giây (\(0 \le t \le T\)) được gọi là thời điểm \(t\).
Bitaro có danh sách những người tham gia cuộc thi. Hiện tại danh sách có \(N\) người. Người thứ \(i\) (\(1 \le i \le N\)) dự định đeo số \(A_i\) và di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc \(S_i\) đơn vị quãng đường mỗi giây.
Dựa trên danh sách, Bitaro đã tính số lần va chạm xảy ra trong cuộc thi. Một va chạm là việc hai người khác nhau có mặt tại cùng một điểm. Chính xác hơn, Bitaro đếm số bộ \((p,q,t)\), trong đó \(p,q\) là các số nguyên thỏa mãn \(0 \le p < q \le L-1\) và \(t\) là số thực thỏa mãn \(0 \le t \le T\), sao cho:
- Có người tham gia đeo số \(p\).
- Có người tham gia đeo số \(q\).
- Người đeo số \(p\) và người đeo số \(q\) ở cùng một điểm tại thời điểm \(t\).
Tuy nhiên, sau đó danh sách được thay đổi \(Q\) lần. Thay đổi thứ \(j\) (\(1 \le j \le Q\)) được mô tả bởi hai số nguyên \(X_j,Y_j\) như sau:
- Nếu trong danh sách hiện tại có người đeo số \(X_j\) và di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc \(Y_j\) đơn vị quãng đường mỗi giây, xóa người đó khỏi danh sách. Nếu không, thêm vào danh sách một người đeo số \(X_j\) và di chuyển quanh hồ theo chiều kim đồng hồ với vận tốc \(Y_j\) đơn vị quãng đường mỗi giây.
Đảm bảo rằng sau mỗi lần thay đổi, danh sách có ít nhất \(2\) người và số đeo của tất cả những người trong danh sách đôi một khác nhau.
Bitaro muốn biết số lần va chạm sẽ xảy ra trong toàn bộ cuộc thi với danh sách người tham gia sau mỗi lần thay đổi. Từ các ràng buộc của bài toán, có thể chứng minh số lần va chạm trong cuộc thi là hữu hạn.
Cho thông tin về cuộc thi và các thay đổi của danh sách, hãy tính số lần va chạm trong cuộc thi với danh sách sau mỗi lần thay đổi, lấy phần dư khi chia cho \(1\,000\,000\,007\).
Dữ liệu vào
Dữ liệu vào có dạng:
N L T
A_1 A_2 ... A_N
S_1 S_2 ... S_N
Q
X_1 Y_1
X_2 Y_2
...
X_Q Y_Q
Dữ liệu ra
In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa phần dư khi chia số lần va chạm trong cuộc thi với danh sách người tham gia sau thay đổi thứ \(j\) cho \(1\,000\,000\,007\).
Ràng buộc
- \(2 \le N\).
- \(N \le L \le 10^9\).
- \(1 \le T \le 10^9\).
- \(0 \le A_i \le L-1\) (\(1 \le i \le N\)).
- \(A_i \ne A_j\) (\(1 \le i < j \le N\)).
- \(1 \le S_i \le 10^9\) (\(1 \le i \le N\)).
- \(1 \le Q\).
- \(N+Q \le 100\,000\).
- \(0 \le X_j \le L-1\) (\(1 \le j \le Q\)).
- \(1 \le Y_j \le 10^9\) (\(1 \le j \le Q\)).
- Sau mỗi lần thay đổi, có ít nhất \(2\) người tham gia.
- Sau mỗi lần thay đổi, các điểm xuất phát của những người tham gia đôi một khác nhau.
- Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
Chấm điểm
- 10 điểm: \(T=1\), \(S_i \le 2\) (\(1 \le i \le N\)), \(Y_j \le 2\) (\(1 \le j \le Q\)).
- 8 điểm: \(N \le 2\,000\), \(Q=1\).
- 11 điểm: \(N \le 2\,000\), \(Q \le 2\,000\).
- 27 điểm: \(Q=1\).
- 34 điểm: \(N+Q \le 78\,000\).
- 10 điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
3 7 2
1 6 3
4 1 6
1
4 2Output
7Giải thích
Sau thay đổi thứ \(1\), có \(4\) người tham gia. Thông tin của từng người như sau:
- Đeo số \(1\), xuất phát tại điểm \(1\) và di chuyển theo chiều kim đồng hồ với vận tốc \(4\) đơn vị quãng đường mỗi giây.
- Đeo số \(6\), xuất phát tại điểm \(6\) và di chuyển theo chiều kim đồng hồ với vận tốc \(1\) đơn vị quãng đường mỗi giây.
- Đeo số \(3\), xuất phát tại điểm \(3\) và di chuyển theo chiều kim đồng hồ với vận tốc \(6\) đơn vị quãng đường mỗi giây.
- Đeo số \(4\), xuất phát tại điểm \(4\) và di chuyển theo chiều kim đồng hồ với vận tốc \(2\) đơn vị quãng đường mỗi giây.
Với danh sách này, trong cuộc thi xảy ra \(7\) va chạm sau:
- Tại thời điểm \(1/4\), người đeo số \(3\) và người đeo số \(4\) cùng ở điểm \(9/2\).
- Tại thời điểm \(3/5\), người đeo số \(3\) và người đeo số \(6\) cùng ở điểm \(33/5\).
- Tại thời điểm \(3/2\), người đeo số \(1\) và người đeo số \(4\) cùng ở điểm \(0\).
- Tại thời điểm \(5/3\), người đeo số \(1\) và người đeo số \(6\) cùng ở điểm \(2/3\).
- Tại thời điểm \(2\), người đeo số \(3\) và người đeo số \(4\) cùng ở điểm \(1\).
- Tại thời điểm \(2\), người đeo số \(3\) và người đeo số \(6\) cùng ở điểm \(1\).
- Tại thời điểm \(2\), người đeo số \(4\) và người đeo số \(6\) cùng ở điểm \(1\).
Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3,4,5,6\).
Ví dụ 2
Input
3 6 1
1 3 4
1 1 1
2
0 2
1 1Output
1
0Giải thích
Sau thay đổi thứ \(1\), có \(4\) người tham gia. Thông tin của từng người như sau:
- Đeo số \(1\), xuất phát tại điểm \(1\) và di chuyển theo chiều kim đồng hồ với vận tốc \(1\) đơn vị quãng đường mỗi giây.
- Đeo số \(3\), xuất phát tại điểm \(3\) và di chuyển theo chiều kim đồng hồ với vận tốc \(1\) đơn vị quãng đường mỗi giây.
- Đeo số \(4\), xuất phát tại điểm \(4\) và di chuyển theo chiều kim đồng hồ với vận tốc \(1\) đơn vị quãng đường mỗi giây.
- Đeo số \(0\), xuất phát tại điểm \(0\) và di chuyển theo chiều kim đồng hồ với vận tốc \(2\) đơn vị quãng đường mỗi giây.
Với danh sách sau thay đổi thứ \(1\), trong cuộc thi xảy ra đúng \(1\) va chạm: tại thời điểm \(1\), người đeo số \(0\) và người đeo số \(1\) cùng ở điểm \(2\).
Sau thay đổi thứ \(2\), có \(3\) người tham gia. Thông tin của từng người như sau:
- Đeo số \(3\), xuất phát tại điểm \(3\) và di chuyển theo chiều kim đồng hồ với vận tốc \(1\) đơn vị quãng đường mỗi giây.
- Đeo số \(4\), xuất phát tại điểm \(4\) và di chuyển theo chiều kim đồng hồ với vận tốc \(1\) đơn vị quãng đường mỗi giây.
- Đeo số \(0\), xuất phát tại điểm \(0\) và di chuyển theo chiều kim đồng hồ với vận tốc \(2\) đơn vị quãng đường mỗi giây.
Với danh sách sau thay đổi thứ \(2\), số lần va chạm trong cuộc thi là \(0\).
Ví dụ này thỏa mãn ràng buộc của các subtasks \(1,3,5,6\).
Ví dụ 3
Input
2 100000 993754689
58683 3478
28489 48682814
1
28482 39599461Output
9265409Giải thích
Sau thay đổi thứ \(1\), có \(3\) người tham gia. Thông tin của từng người như sau:
- Đeo số \(58\,683\), xuất phát tại điểm \(58\,683\) và di chuyển theo chiều kim đồng hồ với vận tốc \(28\,489\) đơn vị quãng đường mỗi giây.
- Đeo số \(3\,478\), xuất phát tại điểm \(3\,478\) và di chuyển theo chiều kim đồng hồ với vận tốc \(48\,682\,814\) đơn vị quãng đường mỗi giây.
- Đeo số \(28\,482\), xuất phát tại điểm \(28\,482\) và di chuyển theo chiều kim đồng hồ với vận tốc \(39\,599\,461\) đơn vị quãng đường mỗi giây.
Với danh sách này, số lần va chạm trong cuộc thi là \(967\,009\,272\,178\). Vì vậy, phần dư khi chia số lần va chạm cho \(1\,000\,000\,007\) là \(9\,265\,409\).
Ví dụ này thỏa mãn ràng buộc của các subtasks \(2,3,4,5,6\).
Ví dụ 4
Input
7 100 100
34 12 46 23 57 63 99
12 34 23 12 34 12 23
5
67 34
99 23
33 34
99 12
23 12Output
330
264
341
440
341Giải thích
Ví dụ này thỏa mãn ràng buộc của các subtasks \(3,5,6\).
Nguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của bài Collision, JOI 2024/2025, vòng loại thứ hai, bài 5 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2025 - Vòng loại 2 (8 Tháng 12., 2024)
Bình luận