Problem Description
Rar the Cat wants to build a wall of L units long. Each unit of the wall can have different height, with the first unit having height H0. Units of the walls are labeled from 0 to L-1.
Rar has a total of M+1 proposals to build the wall. In proposal 0, Rar the Cat has not started planning for the wall yet. Hence, all Hi = 0 for proposal 0.
For each subsequent proposal x, Rar the Cat bases it on an existing proposal Kx, where Kx < x. The heights of the wall in proposal x will be the same as proposal k, except for one contigous
segment of the wall which Rar the Cat will change the height of.
For each proposal x (x < 0), Rar the Cat will provide Kx, Ax, Bx and Cx. This means that proposal x is based on proposal Kx and Rar the Cat
will modify the height of the walls between Ax and Bx by Cx.
In summary, let Hx, i be the height of the ith unit of wall in the xth proposal and kx = Kx.
- H0, i = 0, for all 0 ≤ i < L.
- Hx, i = Hkx, i, for 0 ≤ i < Ax
-
Hx, i = Hkx, i + Cx, for Ax ≤ i ≤ Bx
-
Hx, i = Hkx, i, for Bx < i < L
Given these proposals, Rar the Cat wants you to answer Q queries online. Each query will ask for the maximum height of the wall between a given contigous range of the wall in a certain proposal.
Input
The first line of input will contain 3 integers, L, M and Q.
M lines follow with 4 integers each, the xth line will contain Kx, Ax, Bx and Cx.
Q lines of queries will follow. Each line of query will contain 3 integers, P, X and Y. This means Rar the Cat is asking for the maximum wall height between unit X and Y in proposal P.
Output
For each query, output the maximum height requested on a single line each.
Implementation
You are to code the following functions:
-
void init(int L, int M, int Q)
- L: Length of the wall
- M: Number of proposals in addition to proposal 0
- Q: Number of queries Rar the Cat has
- This function will be called once at the start of the program. You should place all initialization code here.
-
void proposal(int N, int K, int A, int B, int C)
- N: Proposal number of this current proposal
- K: The proposal that the current proposal is based on
- A, B: Range of modification Rar the Cat is going to make
- C: Constant that Rar the Cat would add to the heights between wall unit A and B in this proposal.
- There will be M calls to this function in total.
- It is guaranteed that they will be called in increasing N, from 1 to M.
-
long long max_height(int P, int X, int Y)
- P: Proposal that this query is referring to
- X, Y: Segment of the wall that this query is referring to
- This function will be called Q times, once for each query.
- You are to return the maximum height of the wall in proposal P between unit X and Y inclusive.
Limits
| Subtask |
Score |
L |
M |
Q |
K |
A, B |
C |
P |
X, Y |
| 1 |
8 |
1 ≤ L ≤ 105 |
M = L |
Q ≤ 105 |
K = N-1 |
0 ≤ A = B < L |
-109 ≤ C ≤ 109 |
P = M |
0 ≤ X ≤ Y < L |
| 2 |
13 |
1 ≤ L ≤ 105 |
M ≤ 105 |
Q ≤ 105 |
K = N-1 |
0 ≤ A ≤ B < L |
-109 ≤ C ≤ 109 |
P = M |
0 ≤ X ≤ Y < L |
| 3 |
15 |
1 ≤ L ≤ 109 |
M ≤ 105 |
Q ≤ 105 |
K = N-1 |
0 ≤ A ≤ B < L |
-109 ≤ C ≤ 109 |
P = M |
0 ≤ X ≤ Y < L |
| 4 |
14 |
1 ≤ L ≤ 109 |
M ≤ 105 |
Q ≤ 105 |
K < N |
0 ≤ A = B < L |
C = 1 |
0 ≤ P ≤ M |
0 ≤ X = Y < L |
| 5 |
23 |
1 ≤ L ≤ 105 |
M ≤ 104 |
Q ≤ 104 |
K < N |
0 ≤ A ≤ B < L |
-109 ≤ C ≤ 109 |
0 ≤ P ≤ M |
0 ≤ X ≤ Y < L |
| 6 |
27 |
1 ≤ L ≤ 109
| M ≤ 105 |
Q ≤ 105 |
K < N |
0 ≤ A ≤ B < L |
-109 ≤ C ≤ 109 |
0 ≤ P ≤ M |
0 ≤ X ≤ Y < L |
Sample Testcase 1
Input
5 5 5
0 0 4 5
1 1 1 4
0 2 2 9
2 1 3 6
4 0 2 4
2 1 3
2 0 3
2 1 3
2 2 4
0 1 4
Output
9
9
9
5
0
Sample Testcase 2
Input
20 10 10
0 13 18 3
1 0 7 5
2 12 17 3
2 4 8 2
4 16 17 6
2 4 12 5
3 1 19 9
0 7 13 8
6 0 18 8
3 3 8 1
3 7 8
3 10 17
4 4 17
6 0 10
6 14 18
3 16 17
6 1 19
2 4 19
0 6 12
2 16 18
Output
5
6
7
10
3
6
10
5
0
3
Sample Testcase 3
Input
100 15 15
0 2 68 9
1 10 97 7
2 0 52 6
0 50 53 10
1 23 30 7
0 10 25 2
0 70 77 9
4 41 99 5
1 47 99 9
3 21 70 5
2 38 40 2
1 33 85 1
12 7 54 7
3 0 76 9
5 14 91 9
1 4 84
5 65 67
0 4 61
5 59 68
5 12 64
2 34 43
3 2 55
0 33 92
1 30 98
1 22 35
2 40 85
1 8 68
3 26 90
1 17 85
2 44 56
Output
9
9
0
9
16
16
22
0
9
9
16
9
22
9
16