oj.uz

Submission #993073

# Submission time Handle Problem Language Result Execution time Memory
993073 2024-06-05T09:48:26 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 218 ms 41352 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int N, Q;
int a[200010];
int b[200010];
int vis[200010];
int seg[800010][2][2];
int conlef[800010];
int conrig[800010];
void build(int id, int l, int r){
	if(l==r){
		vis[l]=id;
		if(b[l]>=0){
			conlef[id]=1;
			conrig[id]=1;
		}else{
			conlef[id]=0;
			conrig[id]=0;
		}
		seg[id][1][1]=abs(b[l]);
		return;
	}
	int mid=(l+r)/2;
	build(id*2, l, mid);
	build(id*2+1, mid+1, r);
	conlef[id]=conlef[id*2];
	conrig[id]=conrig[id*2+1];
	if(conrig[id*2]==conlef[id*2+1]){
		seg[id][1][1]=seg[id*2][1][1]+seg[id*2+1][1][1];
		seg[id][1][0]=seg[id*2][1][1]+seg[id*2+1][1][0];
		seg[id][0][1]=seg[id*2][0][1]+seg[id*2+1][1][1];
		seg[id][0][0]=seg[id*2][0][1]+seg[id*2+1][1][0];
	}else{
		seg[id][1][1]=max(seg[id*2][1][1]+seg[id*2+1][0][1], seg[id*2][1][0]+seg[id*2+1][1][1]);
		seg[id][0][1]=max(seg[id*2][0][0]+seg[id*2+1][1][1], seg[id*2][0][1]+seg[id*2+1][0][1]);
		seg[id][1][0]=max(seg[id*2][1][1]+seg[id*2+1][0][0], seg[id*2][1][0]+seg[id*2+1][1][0]);
		seg[id][0][0]=max(seg[id*2][0][0]+seg[id*2+1][0][0], max(seg[id*2][0][0]+seg[id*2+1][1][0], seg[id*2][0][1]+seg[id*2+1][0][0]));
	}
}
void update(int id, int x, int v){
	if(b[x]>=0){
		conlef[id]=1;
		conrig[id]=1;
	}else{
		conlef[id]=0;
		conrig[id]=0;
	}
	seg[id][1][1]=abs(b[x]);
	seg[id][1][0]=0;
	seg[id][0][1]=0;
	seg[id][0][0]=0;
	id/=2;
	while(id){
		conlef[id]=conlef[id*2];
		conrig[id]=conrig[id*2+1];
		if(conrig[id*2]==conlef[id*2+1]){
			seg[id][1][1]=seg[id*2][1][1]+seg[id*2+1][1][1];
			seg[id][1][0]=seg[id*2][1][1]+seg[id*2+1][1][0];
			seg[id][0][1]=seg[id*2][0][1]+seg[id*2+1][1][1];
			seg[id][0][0]=seg[id*2][0][1]+seg[id*2+1][1][0];
		}else{
			seg[id][1][1]=max(seg[id*2][1][1]+seg[id*2+1][0][1], seg[id*2][1][0]+seg[id*2+1][1][1]);
			seg[id][0][1]=max(seg[id*2][0][0]+seg[id*2+1][1][1], seg[id*2][0][1]+seg[id*2+1][0][1]);
			seg[id][1][0]=max(seg[id*2][1][1]+seg[id*2+1][0][0], seg[id*2][1][0]+seg[id*2+1][1][0]);
			seg[id][0][0]=max(seg[id*2][0][0]+seg[id*2+1][0][0], max(seg[id*2][0][0]+seg[id*2+1][1][0], seg[id*2][0][1]+seg[id*2+1][0][0]));
		}
		id/=2;
	}
}
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>N>>Q;
	for(int i=1; i<=N; i++) cin>>a[i];
	for(int i=1; i<N; i++) b[i]=a[i]-a[i+1];
	N--;
	build(1, 1, N);
	for(int i=1; i<=Q; i++){
		int l, r, v; cin>>l>>r>>v;
		b[l-1]-=v; b[r]+=v;
		update(vis[l-1], l-1, b[l-1]);
		update(vis[r], r, b[r]);
		cout<<seg[1][1][1]<<"\n";
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 3 ms 8744 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 4 ms 8756 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 3 ms 8744 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 4 ms 8756 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 188 ms 40788 KB Output is correct
14 Correct 218 ms 40988 KB Output is correct
15 Correct 170 ms 40864 KB Output is correct
16 Correct 191 ms 40996 KB Output is correct
17 Correct 176 ms 40784 KB Output is correct
18 Correct 187 ms 41352 KB Output is correct