Submission #993073

#	Time	Username	Problem	Language	Result	Execution time	Memory
993073		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	218 ms	41352 KiB

Main

#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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55