Submission #1011700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011700		pcc	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	771 ms	64848 KiB

Main

#include <bits/stdc++.h>
using namespace std;


#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define pii pair<int,int>

const int mxn = 2e5+10;
const ll inf = 1e18;
ll arr[mxn];
int N,Q;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	struct node{
		ll dp[3][3];
		node(){
			for(auto &i:dp)for(auto &j:i)j = -inf;
		}
	};
	node seg[mxn*4];
	node pull(node pl,node pr){
		node re = node();
		for(int i = 0;i<=2;i++){
			for(int j = 0;j<=2;j++){
				for(int k = 0;k<=2;k++){
					re.dp[i][j] = max({re.dp[i][j],pl.dp[i][0]+pr.dp[k][j],pl.dp[i][k]+pr.dp[0][j]});
					re.dp[i][j] = max({re.dp[i][j],pl.dp[i][k]+pr.dp[k][j]});
				}
			}
		}
		return re;
	}
	void modify(int now,int l,int r,int p,ll v){
		if(l == r){
			for(auto &i:seg[now].dp)for(auto &j:i)j = -inf;
			seg[now].dp[1][1] = v;
			seg[now].dp[2][2] = -v;
			seg[now].dp[0][0] = 0;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	SEG(){}
#undef ls
#undef rs
#undef mid
};

SEG seg;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	for(int i = N;i>=2;i--){
		arr[i] -= arr[i-1];
		seg.modify(0,2,N,i,arr[i]);
	}

	while(Q--){
		int s,e,v;
		cin>>s>>e>>v;
		arr[s] += v;
		arr[e+1] -= v;
		if(s>1&&s<=N)seg.modify(0,2,N,s,arr[s]);
		if(e+1<=N)seg.modify(0,2,N,e+1,arr[e+1]);
		auto re = seg.seg[0].dp;
		ll ans = 0;
		for(int i = 0;i<3;i++)for(int j = 0;j<3;j++)ans = max(ans,re[i][j]);
		cout<<ans<<'\n';
	}
	return 0;
}

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