제출 #1167443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167443		emptypringlescan	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	399 ms	36204 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int arr[200005],sg[200005];
struct node{
	int s,e,m;
	node *l, *r;
	long long val[2][2];
	void comb(){
		val[0][0]=val[0][1]=val[1][0]=val[1][1]=-1e16;
		for(int a=0; a<2; a++){
			for(int b=0; b<2; b++){
				for(int c=0; c<2; c++){
					for(int d=0; d<2; d++){
						if(sg[m]!=sg[m+1]&&c==1&&d==1) continue;
						val[a][b]=max(val[a][b],l->val[a][c]+r->val[d][b]);
					}
				}
			}
		}
	}
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val[0][0]=val[0][1]=val[1][0]=val[1][1]=-1e16;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			comb();
		}
		else{
			val[0][0]=0;
			val[1][1]=arr[s];
		}
	}
	void update(int S){
		if(s==e){
			val[0][0]=0;
			val[1][1]=arr[s];
			return;
		}
		if(S<=m) l->update(S);
		else r->update(S);
		comb();
	}
} *root;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    int n,q;
    cin >> n >> q;
    int prev=0;
    for(int i=0; i<n; i++){
		int x;
		cin >> x;
		if(i){
			arr[i]=x-prev;
			if(arr[i]<0){
				sg[i]=1;
				arr[i]=-arr[i];
			}
		}
		prev=x;
	}
	root=new node(1,n-1);
	while(q--){
		int a,b;
		long long c;
		cin >> a >> b >> c;
		a--;
		if(a){
			if(sg[a]){
				arr[a]=-arr[a];
				sg[a]=0;
			}
			arr[a]+=c;
			if(arr[a]<0){
				sg[a]=1;
				arr[a]=-arr[a];
			}
			root->update(a);
		}
		if(b<n){
			if(sg[b]){
				arr[b]=-arr[b];
				sg[b]=0;
			}
			arr[b]-=c;
			if(arr[b]<0){
				sg[b]=1;
				arr[b]=-arr[b];
			}
			root->update(b);
		}
		cout << max({root->val[0][0],root->val[0][1],root->val[1][0],root->val[1][1]}) << '\n';
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55