Ciel and Communications System
All submissions for this problem are available.
Ciel has N restaurants on a long straight road.
The coordinate of the i-th restaurant is Xi, and X1 ≤ X2 ≤ ... ≤ XN.
Note that more than one restaurant can have the same coordinate. (They may be in the same building.)
When the i-th restaurant communicates with the j-th restaurant (i < j), a bit strange method is used.
In the method, some towers are used.
Each tower t has four parameters Y[t], R[t], C[t] and T[t].
Here Y[t] denotes the coordinate of the tower, R[t] denotes the range of the tower, C[t] denotes the cost for using the tower if the distance between the tower and the restaurant is 1, and T[t] denotes the type of the tower.
The i-th restaurant can use the tower t if and only if |Xi - Y[t]| ≤ R[t].
Here T[t] is represented as an integer 1 ≤ T[t] ≤ M, where M is the number of types.
For some security reasons, the k-th restaurant can communicate with only the (k±1)-th restaurant directly.
So, it is necessary that the k-th restaurant communicates with the (k+1)-th restaurant for all i ≤ k < j.
For each communication between the k-th and (k+1)-th restaurants, each restaurant chooses the newest available tower.
Let TOWERk be the newest available tower for the k-th restaurant, and let TYPE[k] be the type of TOWERk.
The cost for the communication is C[TOWERk] * |Y[TOWERk] - Xk| + C[TOWERk+1] * |Y[TOWERk+1] - Xk+1|.
If TOWERk ≠ TOWERk+1, then additionally the cost UTYPE[k], TYPE[k+1] is needed.
The total cost of the communication between the i-th and j-th restaurants is the sum of the cost of the communication between the k-th and (k+1)-th restaurants over all i ≤ k < j.
If there should exist some i ≤ k ≤ j such that the k-th restaurant has no available towers, the communication is impossible.
Now Ciel has the history of communications and constructions of towers.
Your task is to calculate the cost for each communication in the history.
In the beginning of the history, you should assume that there are no towers.
The first line contains an integer N, M and Q, where Q denotes the number of the lines of the history.
Then next line contains N integers, where the i-th integer denotes Xi.
Then next M lines contain M integers, where the j-th integer of the i-th line denotes Ui,j
Then next Q lines denote the history of communications and constructions.
The history is composed of the two types of lines.
The line "1 A B" (without quotes) means that the A-th restaurant communicates with the B-th restaurant.
The line "2 Y R C T" (without quotes) means that the tower whose parameters are Y, R, C and T is built.
For each communication, print the cost.
If it is impossible, print "impossible" without quotes.
2 ≤ N ≤ 100000 (105)
1 ≤ M ≤ 50
1 ≤ Q ≤ 50000 (5 * 104)
0 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 1000000000 (109)
0 ≤ Ui,j ≤ 1000000000 (109)
1 ≤ A < B ≤ N
0 ≤ Y ≤ 1000000000 (109)
1 ≤ R ≤ 1000000000 (109)
1 ≤ C ≤ 10000 (104)
1 ≤ T ≤ M
Ui,j = Uj,i
5 2 6 1 3 5 7 10 1 3 3 1 1 1 2 2 5 5 1 1 1 1 2 1 1 4 2 4 1 2 1 1 1 4
impossible 6 10 16
|Tags||cook20, hard, laycurse|
|Time Limit:||0.432806 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.