NAJHQ - Hazzat’s Query
Hazzat is a new guy in computer science. Now he read in 4th semester. Recently he completed the course data structure. After finished data structure course he can realize that those are not enough for his. Every day he fall in a new (data structure) problem and want solve it, but those problem he can’t solve using his know data structure. He want to establish new data structure. But he always failed to establish it. Now help Hazzat to establish a new data structure following problems.
Today Hazzat problem is:
Given a N size array (arr[N]) initialize all the element value to exactly c.
Pseudocode:
for(i=1; i<=N; i++) arr[i] = c;
Today Hazzat want to do 6 types of task.
i) add k to array index u to v
Pseudocode:
for(i=u; i<=v; i++) arr[i] = arr[i] + k;
ii) subtract k from array index u to v
Pseudocode:
for(i=u; i <= v; i++) arr[i] = arr[i] - k;
iii) add k to array index u
Pseudocode:
arr[u] = arr[u] + k;
iv) subtract k from array index u
Pseudocode:
arr[u] = arr[u] - k;
v) reset a array index u with k value
Pseudocode:
arr[u] = k;
vi) find the current value of array index u
Pseudocode:
print arr[u];
Here the array is 1 base index.
Input
Input start with an integer number T (≤ 10), which is number of test cases.
For each test case, first line contains N Q c where N is array size, Q number of queries and c is the initial value of array elements.
Next Q line give Hazzat's tasks
add u v k (add k to array index u to v)
minus u v k (subtract k from array index u to v)
addin u k (add k to array index u)
minusin u k (subtract k from array index u)
reset u k (reset array index u to k)
find u (print current value of array index u)
Constraints
- T ≤ 10
- 1 ≤ N, Q ≤ 10^5
- 1 ≤ u ≤ v ≤ N
- 0 ≤ c, k ≤ 10^9
Output
For each case, print “Case #X” where X is the case number.
After next line print value of array index u where Hazzat want to know. (only for find u task)
Output a blank line between two cases.
Sample
Input: 2 10 3 3 find 4 add 3 7 3 find 5 10 10 3 find 4 add 3 7 2 find 6 minus 3 4 1 find 4 addin 4 5 find 4 minusin 4 2 find 4 find 10 Output: Case #1 3 6 Case #2 3 5 4 9 7 3
Note
Output number may be negative.
Data set is so huge, use faster I/O
hide comments
lenotfound:
2023-01-11 10:44:04
Normal lazytag but AC by colse stream synchronization (~ ̄▽ ̄)~ Last edit: 2023-01-11 10:44:38 |
|
hodobox:
2016-07-06 00:10:19
Lazy needed some constant opti (i.e. minimize # of operations with long long num). These kinds of problems would be a little nicer with +10% TL. |
|
Archit Jain:
2014-12-25 12:11:26
lazy straight forward |
|
RIVU DAS:
2014-12-22 19:22:59
Nice ques! |
|
Archangel:
2014-11-29 08:45:01
@Varun try solving using BIT |
|
vb30:
2014-11-21 12:47:38
Lazy Prop giving TLE ...
|
|
Archangel:
2014-11-18 11:22:58
@Md. Najmuzzaman thank you for this problem :)
|
Added by: | Najmuzzaman |
Date: | 2014-10-26 |
Time limit: | 0.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |