Querying on a Grid
All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Chef is helping out at a volunteering center for teaching. A child comes to Chef with a problem that he is not able to solve and asks Chef for his help. The problem is the following:
Consider an M × N grid graph. The vertices in the grid graph are identified by its row and column number, i.e., for a vertex there are two numbers (i,j) associated with it, where 1 ≤ i ≤ M is its row, and 1 ≤ j ≤ N is its column. There are two types of edges in a grid graph(note that all edges are bidirectional) :
- When i < M, there is an edge of weight down(i, j) connecting (i, j) and (i+1, j);
- When j < N, there is an edge of weight right(i, j) connecting (i, j) and (i, j+1).
Initially, every vertex has a weight of zero.
Define the length of a path to be the sum of weights of all the edges in this path. The shortest path between (i1, j1) and (i2, j2) is the path with the minimum length. Of course, the weights associated with vertices doesn't influence shortest paths at all.
The task in the problem is to process the following 2 types of queries on this graph efficiently :
- i1 j1 i2 j2 c : add c to the weights of all vertices in the shortest path between (i1, j1) and (i2, j2).
- i j : return the weight of vertex (i, j).
Chef is confused with the problem but he wants to help the child. Can you help Chef with this problem?
The first line contains three integers M, N, Q. M and N denotes the graph's size; Q denotes the number of queries.
Next M - 1 lines, each line contains N numbers. The j-th number in the i-th line in this part(i.e., the (i + 1)-th line in total) denotes down(i, j).
Next M lines, each line contains N - 1 numbers. The j-th number in the i-th line in this part(i.e., the (i + M)-th line in total) denotes right(i, j).
Next Q lines, each line contains 3 or 6 numbers, denoting a query.
For each query of type 2, output the weight of required vertex.
- 1 ≤ M ≤ 3
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ down(i,j), right(i,j) ≤ 1012
- In type 1 query :
- 1 ≤ i1, i2 ≤ M
- 1 ≤ j1, j2 ≤ N
- 1 ≤ c ≤ 1013
- The shortest path between (i1, j1) and (i2, j2) is unique.
- In type 2 query :
- 1 ≤ i ≤ M
- 1 ≤ j ≤ N
- Subtask #1 (6 points): N, Q ≤ 103
- Subtask #2: (11 points): M = 1.
- Subtask #3: (30 points): M = 2.
- Subtask #4: (24 points):
- down(i,j) and right(i,j) are uniformly randomly generated from [1,3 × 1010].
- Queries are also randomly generated.
- There is only one test file for this subtask.
- Subtask #5: (29 points):: Original Constraints
Input: 3 3 11 1 1 5 2 10 6 1 4 1 13 6 5 1 2 2 3 3 1 1 2 2 1 3 2 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 Output: 0 2 2 1 3 0 1 1 1
Example case 1. See picture below.
The shortest path between (2,2) and (3,3) is (2,2)->(2,1)->(3,1)->(3,2)->(3,3). We add 1 to these 5 vertices.
The shortest path between (2,2) and (1,3) is (2,2)->(1,2)->(1,3). We add 2 to these 3 vertices.
Note that the shortest path between (1,1) and (2,2) is not unique. However, the queried paths are (2,2)-(3,3) and (2,2)-(1,3), and the shortest paths of these pairs of points are unique, so this data is valid.
|Tags||divide-and-conq, hard, r_64, sept17, shortest-path|
|Time Limit:||7 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.