D. Three Sequences SOLUTION CODEFORCES

Three Sequences SOLUTION

You are given a succession of n numbers a1,a2,… ,an. You need to develop two arrangements of whole numbers b and c with length n that fulfill: 
 
for each I (1≤i≤n) bi+ci=ai 
 
b is non-diminishing, which implies that for each 1<i≤n, bi≥bi−1 must hold 
 
c is non-expanding, which implies that for each 1<i≤n, ci≤ci−1 must hold 
 
You need to limit max(bi,ci). At the end of the day, you need to limit the most extreme number in successions b and c. 
 
Additionally there will be q changes, the I-th change is portrayed by three numbers l,r,x. You should add x to al,al+1,… ,ar. 
 
You need to locate the base conceivable estimation of max(bi,ci) for the underlying arrangement and for succession after each change. 
 
Information 
 
The main line contains a whole number n (1≤n≤105). 
 
The secound line contains n numbers a1,a2,… ,a (1≤i≤n, −109≤ai≤109). 
 
The third line contains a number q (1≤q≤105). 
 
Every one of the following q lines contains three numbers l,r,x (1≤l≤r≤n,−109≤x≤109), desribing the following change. 
 
Yield 
 
Print q+1 lines. 
 
On the I-th (1≤i≤q+1) line, print the response to the issue for the succession after i−1 changes. 
 
Models 
 
inputCopy 
 
 
2 – 1 7 3 
 
 
2 4 – 3 
 
3 4 2 
 
outputCopy 
 
 
 
 
inputCopy 
 
 
– 9 – 10 – 9 – 6 – 5 4 
 
 
2 6 – 9 
 
1 2 – 10 
 
4 6 – 3 
 
outputCopy 
 
 
 
 
 
inputCopy 
 
 
 
 
1 – 1 
 
1 – 1 
 
outputCopy 
 
 
 
– 1 
 
Note 
 
In the main test: 
 
The underlying grouping a=(2,−1,7,3). Two successions b=(−3,−3,5,5),c=(5,2,2,−2) is a potential decision. 
 
After the primary change a=(2,−4,4,0). Two successions b=(−3,−3,5,5),c=(5,−1,−1,−5) is a potential decision. 
 
After the second change a=(2,−4,6,2). Two arrangements b=(−4,−4,6,6),c=(6,0,0,−4) is a potential decision.
 

Leave a Comment

close
error: Content is protected !!