query
Training Tasks
English (ISC)
Easy Query
You want to solve the following easy data structure task. You work on an infinite 2D integer lattice.
Each lattice point (X, Y ) initially has weight 0. You must process a sequence of operations of two
types:
Update (x, y, d, w): for every lattice point (X, Y ) satisfying ∣X − x∣ < d and ∣Y − y∣ < d,
add
w ⋅ (d − max(∣X − x∣, ∣Y − y∣))
to its weight.
Query [x1 , x2 ] × [y1 , y2 ]: return the sum of weights of all lattice points (X, Y ) with
x1 ≤ X ≤ x2 and y1 ≤ Y ≤ y2 , taken modulo 230
.
All coordinates and parameters are integers.
Implementation Details
You should implement the following procedure:
std::vector<unsigned> lattice_pyramid(
int M,
std::vector<int> T,
std::vector<long long> A,
std::vector<long long> B,
std::vector<long long> C,
std::vector<long long> D
)
: number of operations.
M
T[i](for ): the operation type;
0 ≤ i < M 1for update,
2for query.
For each index
i:
If
T[i] == 1(update), then the parameters are
,
x = A[i] ,
y = B[i] ,
d = C[i] .
w = D[i]
query (1 of 4)
If
T[i] == 2(query), then the parameters are
,
x1 = A[i] ,
x2 = B[i] ,
y1 = C[i] .
y2 = D[i]
The function must process the operations in order and return a vector containing, in order,
the answers to all query operations, each reduced modulo 230 .
The return type uses
uint32_t ; each value must be in the range 0 ≤ answer < 230
.
Notes.
The lattice is infinite (all integer pairs (X, Y )), but only finitely many points are affected by
any update.
The inequalities in updates are strict: ∣X − x∣ < d and ∣Y − y∣ < d.
Queries are inclusive on both ends in each coordinate.
Constraints
1 ≤ M ≤ 100 000
For every update (x, y, d, w): 1 ≤ x, y, d, w ≤ 108
For every query [x1 , x2 ] × [y1 , y2 ]: 1 ≤ x1 ≤ x2 ≤ 108 , 1 ≤ y1 ≤ y2 ≤ 108
All inputs are integers.
The sequence of operations can be arbitrary unless restricted by a subtask.
Subtasks
Subtask Score Additional Constraints
1 3 M ≤ 1,000
2 4 M ≤ 20,000
3 5 M ≤ 40,000
4 6 M ≤ 60,000
5 6 M ≤ 80,000
All updates appear before any query (i.e., for every query, there is no
6 18
update after it).
7 9 x2 − x1 ≤ 5, y2 − y1 ≤ 5, and d ≤ 5.
8 8 d ≤ 5.
9 41 No additional constraints.
Example
Consider the following sequence of operations:
query (2 of 4)
M = 5
1 3 4 5 1
2 1 4 3 5
1 2 4 2 2
2 4 5 3 5
1 4 4 4 8
Calling
lattice_pyramid(
5,
[1, 2, 1, 2, 1],
[3, 1, 2, 4, 4],
[4, 4, 4, 5, 4],
[5, 3, 2, 3, 4],
[1, 5, 2, 5, 8]
)
should return
[46, 21]
Sample Grader
Input format
M
(op_1)
(op_2)
...
(op_M)
Each operation is a line of five integers:
Update:
1 x y d w
Query:
2 x1 x2 y1 y2
Output format
query (3 of 4)
K
ans_1
ans_2
...
ans_K
K is the number of queries (
K equals the length of the vector returned by
).
lattice_pyramid
Each
ans_jis the
j-th element returned by the function, modulo 230
.
The grader reads all operations, builds the arrays , calls
T, A, B, C, D lattice_pyramid(M,
, and prints the answers in order.
T, A, B, C, D)
query (4 of 4)