Chọn ĐTQG An Giang 2026 - Đèn lưới
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Alice thiết lập một hệ thống hiển thị dạng bảng gồm ~M~ dòng (đánh số từ ~1~ đến ~M~ từ trên xuống dưới) và ~N~ cột (đánh số từ ~1~ đến ~N~ từ trái sang phải). Tại mỗi ô thuộc dòng ~i~ ~(1 \le i \le M)~ và cột ~j~ ~(1 \le j \le N)~ đặt một bóng đèn ban đầu ở trạng thái tắt.
Để kiểm tra hệ thống điều khiển, Alice thực hiện ~Q~ thao tác biến đổi trạng thái. Thao tác thứ ~s~ ~(1 \le s \le Q)~ tác động lên một vùng hình chữ nhật có ô góc trên-bên trái là ~(x_s, y_s)~ và ô góc dưới-bên phải là ~(u_s, v_s)~. Khi thực hiện thao tác này, tất cả các đèn nằm trong vùng hình chữ nhật sẽ đảo trạng thái: đèn đang tắt trở thành bật, đèn đang bật trở thành tắt.
Yêu cầu: Cho kích thước bảng ~M, N~ và ~Q~ thao tác, hãy giúp Alice đếm số lượng đèn ở trạng thái bật sau khi thực hiện ~Q~ thao tác.
Input
Dòng đầu tiên chứa ba số nguyên dương ~M, N, Q~ ~(M \times N \le 10^6; Q \le 10^6)~.
Dòng thứ ~s~ ~(1 \le s \le Q)~ trong ~Q~ dòng tiếp theo chứa bốn số nguyên ~x_s, y_s, u_s, v_s~ ~(1 \le x_s \le u_s \le M; 1 \le y_s \le v_s \le N)~ mô tả thao tác thứ ~s~.
Output
Ghi ra một số nguyên duy nhất là số lượng đèn ở trạng thái bật sau khi thực hiện ~Q~ thao tác.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~40\%~ | ~M = 1; N, Q \le 100~ |
| 2 | ~30\%~ | ~M = 1~ |
| 3 | ~30\%~ | Không có giới hạn gì thêm |
Sample Input 1
2 2 2
1 1 2 2
2 2 2 2
Sample Output 1
3
Bình luận
Các bạn bị lỗi RTE, thì đọc lí do ở đây nhé. Vì $N \times M \le 10^6$, các bạn nên dùng CTDL động như vector khai báo như sau:
hay
RLE rồi cứu với
Mình đoán là bạn đang dùng a[1e6][1e6]. Nếu bạn làm như thế thì sẽ bị RTE lắm.
Thay vào đó bạn có thể dùng như dưới là AC nhé:
vector< vector<int>> a;
a.resize(m + 1, vector<int>(n + 1));