제출 #1084615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084615		PieArmy	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	287 ms	44764 KiB

Main

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

struct Seg{
	int n;
	vector<ll>arr;
	vector<array<array<ll,2>,2>>mx;
	vector<int>sag,sol;
	void comb(int node,int left,int right){
		sag[node]=sag[node*2+1];
		if(sag[node]==0)sag[node]=sag[node*2];
		sol[node]=sol[node*2];
		if(sol[node]==0)sol[node]=sol[node*2+1];
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				mx[node][i][j]=0;
				for(int l=0;l<2;l++){
					for(int r=0;r<2;r++){
						if(sol[node*2+1]+sag[node*2]==0&&l&&r){
							continue;
						}
						mx[node][i][j]=max(mx[node][i][j],mx[node*2][i][l]+mx[node*2+1][r][j]);
					}
				}
			}
		}
	}
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			mx[node][0][0]=mx[node][0][1]=mx[node][1][0]=0;
			mx[node][1][1]=abs(arr[left]);
			if(arr[left]<0)sag[node]=-1;
			if(arr[left]==0)sag[node]=0;
			if(arr[right]>0)sag[node]=1;
			sol[node]=sag[node];
			return;
		}
		build(node*2,left,mid);build(node*2+1,mid+1,right);
		comb(node,left,right);
	}
	Seg(vector<ll>v){
		arr=v;
		n=arr.size();
		mx.resize(n<<2);
		sag.resize(n<<2);
		sol.resize(n<<2);
		build();
	}
	ll tar,x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			arr[left]+=x;
			mx[node][0][0]=mx[node][0][1]=mx[node][1][0]=0;
			mx[node][1][1]=abs(arr[left]);
			if(arr[left]<0)sag[node]=-1;
			if(arr[left]==0)sag[node]=0;
			if(arr[right]>0)sag[node]=1;
			sol[node]=sag[node];
			return;
		}
		if(tar>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		comb(node,left,right);
	}
	void update(ll l,ll r){
		tar=l;
		x=r;
		up();
	}
};

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n,q;cin>>n>>q;
	vector<ll>v;
	ll las;cin>>las;v.pb(0);
	for(int i=1;i<n;i++){
		ll x;cin>>x;
		v.pb(x-las);
		las=x;
	}
	Seg seg(v);
	while(q--){
		int l,r;ll x;
		cin>>l>>r>>x;
		if(l!=1){
			seg.update(l-1,x);
		}
		if(r!=n){
			seg.update(r,-x);
		}
		cout<<seg.mx[1][1][1]<<endl;
	}
}

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