NKMOBILE - IOI01 Mobiles

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkmobile


Các trạm di động thế hệ 4 ở Tampere hoạt động như sau. Cả khu vực được chia thành các ô vuông. Các ô vuông tạo thành một bảng SxS với các dòng và cột đánh số từ 0 đến S-1. Mỗi ô vuông chứa một trạm di động. Số điện thoại di động hoạt động trong một ô vuông có thể thay đổi vì điện thoại có thể chuyển sang ô vuông khác hoặc thay đổi trạng thái bật/tắt. Khi có thay đổi, mỗi trạm di động sẽ thông báo cho trung tâm. Tại một số thời điểm, trung tâm cần truy vấn tổng số điện thoại đang hoạt động trong một vùng diện tích hình chữ nhật nào đó.

Hãy giúp trung tâm nhận các thông báo từ trạm và trả lời các truy vấn.

Dữ liệu

Gồm nhiều dòng, mỗi dòng chứa các chỉ thị cho chương trình. Có 3 loại chỉ thị 0, 1, 2, 3 nhận các tham số và thực hiện các nhiệm vụ tương ứng như sau:

Chỉ thịTham sốÝ nghĩa
0SKhởi tạo bảng SxS chứa toàn bộ số 0. Chỉ thị này chỉ được cho một lần duy nhất ở đầu chương trình.
1X Y ACộng A và số điện thoại hoạt động ở ô vuông (X, Y). A có thể âm hoặc dương.
2L B R TTruy vấn tổng số điện thoại hoạt động ở các ô vuông (X, Y) với L ≤ X ≤ R, B ≤ Y ≤ T
3.Kết thúc chương trình. Chỉ thị này chỉ được cho một lần duy nhất ở cuối chương trình.

Giá trị của một ô luôn không âm tại mỗi thời điểm. Các chỉ số bắt đầu từ 0, nghĩa là với một bảng 4x4, ta có 0 ≤ X ≤ 3, 0 ≤ Y ≤ 3.

Kết qủa

Với mỗi chỉ thị loại 2, in ra một dòng gồm một số nguyên dương trả lời cho truy vấn tương ứng.

Giới hạn

  • 1 ≤ S ≤ 1024
  • Giá trị của một ô tại mọi thời điểm luôn thuộc phạm vi [0, 32767].
  • -32768 ≤ A ≤ 32767
  • Số chỉ thị thuộc phạm vi [3, 60002].
  • Tổng số điện thoại trên toàn bộ bảng không vượt quá 230.

Ví dụ

Dữ liệu
0 4  		
1 1 2 3  		
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3

Kết qủa
3
4

Được gửi lên bởi:Jimmy
Ngày:2007-12-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOI 2001 - Finland

hide comments
2019-10-18 10:48:55
Bài này có thể mở rộng lên n=1e5
https://ideone.com/NxuBXJ
2018-12-25 09:56:56
ez BIT 2D
but i wonder can i do it with BIT 1D like ccost ???

Last edit: 2018-12-25 10:05:58
2018-05-03 03:05:38
Chả hiểu các ông làm thế nào chứ tôi trâu cũng AC :D
2018-01-06 12:59:47
BIT 2D 3 đấm AC sai vụ hàng cột L R B T -_-

Last edit: 2018-01-06 13:02:37
2017-10-18 12:57:48
1 Đấm AC BIT2D (lần đầu làm BIT2D) :>
- frostpixel aka.How 2 AC
2016-10-07 11:43:25 THK6
BIT2D -> 1 đấm AC :3
2016-10-05 12:08:55
IT 2d có 40 :'( , chắc code chưa tối ưu
2016-10-01 17:51:56
IT2D -> tle
BIT2D -> AC :3
2016-05-22 15:53:27 Lê Thanh Phú
IT2D time >1s

Last edit: 2016-06-28 16:19:41
2016-05-22 10:00:40 Lê Thanh Phú
Bai nay cai bang BIT 2D cung hay
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.