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 H_{0}. 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 H_{i} = 0 for proposal 0.
For each subsequent proposal x, Rar the Cat bases it on an existing proposal K_{x}, where K_{x} < 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 K_{x}, A_{x}, B_{x} and C_{x}. This means that proposal x is based on proposal K_{x} and Rar the Cat will modify the height of the walls between A_{x} and B_{x} by C_{x}.
In summary, let H_{x, i} be the height of the i^{th} unit of wall in the x^{th} proposal and kx = K_{x}.
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.
The first line of input will contain 3 integers, L, M and Q.
M lines follow with 4 integers each, the x^{th} line will contain K_{x}, A_{x}, B_{x} and C_{x}.
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.
For each query, output the maximum height requested on a single line each.
You are to code the following functions:
void init(int L, int M, int Q)
void proposal(int N, int K, int A, int B, int C)
long long max_height(int P, int X, int Y)
Subtask | Score | L | M | Q | K | A, B | C | P | X, Y |
---|---|---|---|---|---|---|---|---|---|
1 | 8 | 1 ≤ L ≤ 10^{5} | M = L | Q ≤ 10^{5} | K = N-1 | 0 ≤ A = B < L | -10^{9} ≤ C ≤ 10^{9} | P = M | 0 ≤ X ≤ Y < L |
2 | 13 | 1 ≤ L ≤ 10^{5} | M ≤ 10^{5} | Q ≤ 10^{5} | K = N-1 | 0 ≤ A ≤ B < L | -10^{9} ≤ C ≤ 10^{9} | P = M | 0 ≤ X ≤ Y < L |
3 | 15 | 1 ≤ L ≤ 10^{9} | M ≤ 10^{5} | Q ≤ 10^{5} | K = N-1 | 0 ≤ A ≤ B < L | -10^{9} ≤ C ≤ 10^{9} | P = M | 0 ≤ X ≤ Y < L |
4 | 14 | 1 ≤ L ≤ 10^{9} | M ≤ 10^{5} | Q ≤ 10^{5} | K < N | 0 ≤ A = B < L | C = 1 | 0 ≤ P ≤ M | 0 ≤ X = Y < L |
5 | 23 | 1 ≤ L ≤ 10^{5} | M ≤ 10^{4} | Q ≤ 10^{4} | K < N | 0 ≤ A ≤ B < L | -10^{9} ≤ C ≤ 10^{9} | 0 ≤ P ≤ M | 0 ≤ X ≤ Y < L |
6 | 27 | 1 ≤ L ≤ 10^{9} | M ≤ 10^{5} | Q ≤ 10^{5} | K < N | 0 ≤ A ≤ B < L | -10^{9} ≤ C ≤ 10^{9} | 0 ≤ P ≤ M | 0 ≤ X ≤ Y < L |
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
9 9 9 5 0
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
5 6 7 10 3 6 10 5 0 3
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
9 9 0 9 16 16 22 0 9 9 16 9 22 9 16
Subtask | Score |
---|---|
1 | 8 |
2 | 13 |
3 | 15 |
4 | 14 |
5 | 23 |
6 | 27 |
7 | 0 |