Hướng dẫn cho AtCoder ABC221 D - Trò chơi trực tuyến
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Gộp các sự kiện cùng ngày
Người chơi thứ \(i\) làm số người đăng nhập tăng \(1\) vào ngày \(A_i\) và giảm \(1\) vào ngày \(A_i+B_i\). Ngày giảm nằm ngay sau ngày cuối cùng được tính.
Sắp các sự kiện theo ngày. Nếu có active người trong khoảng từ ngày previous tới trước ngày sự kiện tiếp theo day, cộng day - previous vào đáp án của active. Sau đó áp dụng mọi thay đổi tại day. Khi xử lý nhiều sự kiện cùng ngày lần lượt, các khoảng giữa chúng có độ dài \(0\), nên kết quả vẫn đúng.
Chỉ in các đáp án từ \(1\) tới \(N\); số ngày không ai đăng nhập không được hỏi. C++ dùng long long cho ngày sự kiện và số ngày.
Chứng minh
Mỗi người bắt đầu được tính đúng tại \(A_i\) và ngừng được tính tại \(A_i+B_i\), nên số người sau các sự kiện ở ngày \(x\) đúng với mọi ngày nguyên từ \(x\) tới trước ngày sự kiện tiếp theo. Các khoảng đó rời nhau và chứa mọi ngày có người đăng nhập. Cộng độ dài từng khoảng theo số người cho đúng toàn bộ kết quả.
Có \(2N\) sự kiện. Thời gian là \(O(N\log N)\) và bộ nhớ là \(O(N)\).
Bình luận