import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static class Node{
long skipl = 0, skipr = 0, skiplr = 0, skipnone;
}
static long[] dif;
static Node[] seg;
static void construct(int node, int l, int r){
if(l == r) return;
if(r - l == 1){
seg[node].skipnone = Math.abs(dif[l]);
seg[node].skipl = 0L;
seg[node].skipr = 0L;
seg[node].skiplr = 0L;
}else{
int mid = (l + r)/2;
construct(node*2+1,l,mid);
construct(node*2+2,mid,r);
merge(mid, node, node*2+1, node*2+2);
}
}
static void update(int node, int l, int r, int ind, long v){
if(ind < l || r <= ind) return;
if(r - l == 1){
seg[node].skipnone = Math.abs(v);
return;
}
int mid = (l + r)/2;
update(node*2+1, l, mid, ind, v);
update(node*2+2, mid, r, ind, v);
merge(mid, node, node*2+1, node*2+2);
}
static void merge(int mid, int node, int lnode, int rnode){
if((dif[mid - 1] > 0 && dif[mid] > 0) || (dif[mid - 1] < 0 && dif[mid] < 0) || (dif[mid] == 0 || dif[mid - 1] == 0)){
seg[node].skipnone = seg[lnode].skipnone + seg[rnode].skipnone;
seg[node].skipl = seg[lnode].skipl + seg[rnode].skipnone;
seg[node].skipr = seg[lnode].skipnone + seg[rnode].skipr;
seg[node].skiplr = seg[lnode].skipl + seg[rnode].skipr;
}else{
seg[node].skipnone = Math.max(seg[lnode].skipnone + seg[rnode].skipl, seg[lnode].skipr + seg[rnode].skipnone);
seg[node].skipl = Math.max(seg[lnode].skipl + seg[rnode].skipr, seg[lnode].skiplr + seg[rnode].skipnone);
seg[node].skipr = Math.max(seg[lnode].skipnone + seg[rnode].skiplr, seg[lnode].skipr + seg[rnode].skipr);
seg[node].skiplr = Math.max(seg[lnode].skiplr + seg[rnode].skipr, seg[lnode].skipl + seg[rnode].skiplr);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
dif = new long[n];
seg = new Node[4 * n];
for (int i = 0; i < 4 * n; i++) seg[i] = new Node();
dif[n - 1] = 0;
st = new StringTokenizer(br.readLine());
long prev = Long.parseLong(st.nextToken());
for (int i = 0; i < n - 1; i++) {
long cur = Long.parseLong(st.nextToken());
dif[i] = cur - prev;
prev = cur;
}
construct(0, 0, n-1);
for (int i = 0; i < q; i++) {
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken()) - 1, r = Integer.parseInt(st.nextToken()) - 1;
long v = Long.parseLong(st.nextToken());
if(n != 1){
if(l != 0){
l--;
dif[l] += v;
}
if(r != n - 1){
dif[r] -= v;
}else{
r--;
}
update(0, 0, n - 1, l, dif[l]);
update(0, 0, n - 1, r, dif[r]);
}
System.out.println(seg[0].skipnone);
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
8512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
8512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
8512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
