trang chủ / đề bài / icpc26_mn_b

Lò phản ứng tinh thể

Đề bài

Mô tả

Một cơ sở nghiên cứu có một lò phản ứng tinh thể ba chiều gồm N×M×P ô. Mỗi ô (x,y,z), với 1≤x≤N, 1≤y≤M và 1≤z≤P, ban đầu chứa năng lượng bằng không. Ta hiểu x là tọa độ hàng, y là tọa độ cột và z là tọa độ lớp.

Lò phản ứng được kích hoạt Q lần. Trong một lần kích hoạt, một nguồn năng lượng được đặt tại góc (x1,y1,z1) và tác động lên mọi ô nằm trong hình hộp chữ nhật có các cạnh song song với các trục [x1,x2]×[y1,y2]×[z1,z2].

Tại ô nguồn (x1,y1,z1), lần kích hoạt này đóng góp S đơn vị năng lượng. Xuất phát từ góc đó, mỗi bước một ô theo chiều dương của trục X làm phần đóng góp tăng thêm A, mỗi bước theo chiều dương của trục Y làm phần đóng góp tăng thêm B, và mỗi bước theo chiều dương của trục Z làm phần đóng góp tăng thêm C. Nói cách khác, ô (x,y,z) trong hình hộp nhận được S+A(x−x1)+B(y−y1)+C(z−z1) đơn vị năng lượng.

Tác động chỉ tồn tại bên trong hình hộp đã cho. Nếu nhiều nguồn cùng tác động lên một ô, mọi phần đóng góp của chúng được cộng lại. Các lần kích hoạt có thể chồng lên nhau và các phần đóng góp được cộng dồn. S, A, B và C có thể âm.

Sau khi cả Q lần kích hoạt đã được thực hiện, hệ thống điều khiển kiểm tra L ô (không có lần kiểm tra nào xen giữa các lần kích hoạt). Với mỗi ô được kiểm tra, hãy cho biết năng lượng cuối cùng chứa trong ô đó. Các ô được kiểm tra là tùy ý, không tuân theo một phân bố nào.

Dữ liệu vào

  • Dòng đầu tiên chứa năm số nguyên N, M, P, Q và L: kích thước lò phản ứng, số lần kích hoạt và số ô được kiểm tra (1≤N,M,P≤200, N×M×P≤2·106, 1≤Q≤4·105, 1≤L≤106).
  • Mỗi dòng trong Q dòng tiếp theo chứa mười số nguyên x1,y1,z1,x2,y2,z2,S,A,B và C (1≤x1≤x2≤N, 1≤y1≤y2≤M, 1≤z1≤z2≤P, |S|,|A|,|B|,|C|≤106), mô tả một lần kích hoạt với góc nguồn (x1,y1,z1), góc đối diện (x2,y2,z2), năng lượng ban đầu S và các lượng tăng mỗi bước A, B, C lần lượt theo chiều dương của các trục X, Y, Z. Mọi đầu mút của hình hộp đều được tính (đoạn đóng).
  • Mỗi dòng trong L dòng tiếp theo chứa ba số nguyên x, y và z (1≤x≤N, 1≤y≤M, 1≤z≤P): tọa độ của một ô được kiểm tra. Các tọa độ kiểm tra có thể lặp lại.

Dữ liệu bảo đảm năng lượng cuối cùng của mọi ô vừa trong kiểu số nguyên có dấu 64 bit.

Dữ liệu ra

In ra L dòng. Dòng thứ i chứa năng lượng cuối cùng của ô được kiểm tra thứ i, theo đúng thứ tự xuất hiện của các tọa độ kiểm tra trong dữ liệu vào.

Ràng buộc

  • 1≤N,M,P≤200, N×M×P≤2·106.
  • 1≤Q≤4·105, 1≤L≤106.
  • 1≤x1≤x2≤N, 1≤y1≤y2≤M, 1≤z1≤z2≤P.
  • |S|,|A|,|B|,|C|≤106.
  • 1≤x≤N, 1≤y≤M, 1≤z≤P.

Ví dụ

Input Output Giải thích
2 2 3 2 4
1 1 1 2 2 3 10 100 10 1
2 1 2 2 2 3 5 0 2 3
1 1 1
2 1 2
2 2 3
1 2 2
10
116
132
21
Lần kích hoạt thứ nhất có nguồn tại (1,1,1), đóng góp 10 tại đó; mỗi bước theo X thêm 100, theo Y thêm 10, theo Z thêm 1. Chẳng hạn nó đóng góp 111 tại (2,1,2) và 122 tại (2,2,3). Nguồn thứ hai ở (2,1,2), đóng góp 5 tại ô đó; mỗi bước theo Y thêm 2, theo Z thêm 3. Vì vậy năng lượng cuối cùng tại bốn ô được kiểm tra là 10, 116, 132 và 21.
1 3 2 2 3
1 1 1 1 3 2 -5 7 -2 4
1 2 2 1 3 2 100 0 -50 9
1 1 1
1 3 2
1 2 2
-5
45
97
Ví dụ bổ sung (không có trong đề gốc). Lần kích hoạt thứ nhất phủ cả lò: ô (1,3,2) nhận −5+2·(−2)+1·4=−5 và ô (1,2,2) nhận −5−2+4=−3. Lần thứ hai có nguồn tại (1,2,2): ô đó nhận 100, ô (1,3,2) nhận 100−50=50. Ô (1,1,1) chỉ thuộc lần thứ nhất.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0