Submission #993050

#	Time	Username	Problem	Language	Result	Execution time	Memory
993050		vjudge1	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	316 ms	26964 KiB

Main

#include <bits/stdc++.h>
#define int long long 
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int> 

using namespace std;

int a[200005], p[200005];
struct ha{
	int oo , ox , xo , xx;
	void mix(ha& a , ha& b, int mid , int l , int r){
		oo = max({a.ox+b.xo , a.ox+b.oo , a.oo+b.xo});
		ox = max({a.ox+b.ox , a.oo+b.xx , a.ox+b.xx});
		xo = max({a.xx+b.xo , a.xx+b.oo , a.xo+b.xo });
		xx = max({a.xx+b.xx , a.xo+b.xx , a.xo +b.xx , a.xx+b.ox});
		if(((p[mid]>= 0 && p[mid+1]>=0) || (p[mid]<= 0 && p[mid+1] <= 0))){
			
			oo = max({oo , a.ox +b.xo , a.oo +b.xo ,a.oo +b.oo , a.ox+b.oo});
			ox = max({ox , a.ox +b.xx , a.oo +b.xx, a.oo+b.ox, a.ox +b.ox});
			xo = max({xo , a.xx+b.xo , a.xx+b.oo , a.xo +b.xo , a.xo +b.oo});
			xx = max({xx , a.xx+b.xx , a.xx+b.ox , a.xo+b.xx , a.xo+b.ox} );
		}
	}
	int mx(){
		return max({oo , ox , xo , xx});
	}
};
ha seg[800005];
int gg = -1e18;
void build(int id , int l , int r){
	if(l==r){
		seg[id] = {abs(p[l]), 0, 0 ,0};
		return ;
	}
	int mid = (l+r)/2;
	build(id*2 , l , mid);
	build(id*2+1 , mid+1 , r);
	seg[id].mix(seg[id*2], seg[id*2+1], mid, l , r);
}
void up(int id , int l , int r , int u){
	if(l>u||r < u) return ;
	if(l==r){
		seg[id].oo = abs(p[l]);
		return ;
	}
	int mid = (l+r)>>1;
	up(id*2 , l , mid , u );
	up(id*2+1 , mid+1 , r , u );
	seg[id].mix(seg[id*2], seg[id*2+1], mid, l , r);
}
signed main(){
//	freopen("optmilk.in","r" , stdin );
//	freopen("optmilk.out","w" , stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n , q , l , r , x; 
	cin >> n >> q ; 
	for(int i = 1 ;i <= n ; i++){
		cin >> a[i];
		if(i > 1){
			p[i-1] =a[i]-a[i-1]; 
		}
	}
	n--;
	build(1 , 1 , n );
//	cout << seg[2].ox<<" "<<seg[3].xx<<'\n';
	while(q	--){
		cin >> l >> r >> x;
		p[l-1]+=x;
		p[r]-=x;
		up(1 , 1 , n , l-1 );
		up(1 , 1 , n , r );
		cout <<seg[1].mx() <<'\n';
	}

}

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