제출 #1192478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192478		boclobanchat	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	467 ms	42944 KiB

Main

#include<iostream>
using namespace std;
struct node { long long dp[3][3]; };
const int MAXN=(1<<18)+5;
const long long INF=1e18;
node seg[MAXN*4],cs;
long long A[MAXN],V[3],W[3];
int F[MAXN];
void maximize(long long& a,long long b)
{
	if(a<b) a=b;
}
node merge(node a,node b)
{
	node c;
	for(int i=0;i<3;i++)
	{
		V[i]=a.dp[i][0],W[i]=b.dp[0][i];
		maximize(V[i],a.dp[i][1]);
		maximize(V[i],a.dp[i][2]);
		maximize(W[i],b.dp[1][i]);
		maximize(W[i],b.dp[2][i]);
	}
	for(int i=0;i<3;i++) for(int j=0;j<3;j++)
	{
		c.dp[i][j]=a.dp[i][0]+W[j];
		maximize(c.dp[i][j],V[i]+b.dp[0][j]);
		maximize(c.dp[i][j],a.dp[i][1]+b.dp[1][j]);
		maximize(c.dp[i][j],a.dp[i][2]+b.dp[2][j]);
	}
	return c;
}
void build(int l,int r,int pos)
{
	if(l>r) return ;
	if(l==r)
	{
		F[l]=pos;
		seg[pos].dp[0][1]=seg[pos].dp[0][2]=seg[pos].dp[1][0]=seg[pos].dp[1][2]=seg[pos].dp[2][0]=seg[pos].dp[2][1]=-INF;
		seg[pos].dp[0][0]=0;
		seg[pos].dp[1][1]=A[l];
		seg[pos].dp[2][2]=-A[l];
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,pos*2);
	build(mid+1,r,pos*2+1);
	seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
void update(int i,int val)
{
	seg[i=F[i]].dp[1][1]+=val;
	seg[i].dp[2][2]-=val;
	while(i>>=1) seg[i]=merge(seg[i*2],seg[i*2+1]);
}
long long get(int l,int r,int lg)
{
	node ans=cs;
	l--;
	for(int i=0;i<=lg;i++) if((l&(1<<i))&&l+(1<<i)<=r) ans=merge(ans,seg[(l>>i)+(1<<(lg-i))]),l+=(1<<i);
	for(int i=lg;i+1;i--) if(l+(1<<i)<=r) ans=merge(ans,seg[(l>>i)+(1<<(lg-i))]),l+=(1<<i);
	long long a=0;
	for(int i=0;i<3;i++) for(int j=0;j<3;j++) maximize(a,ans.dp[i][j]);
	return a;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<n;i++) A[i]-=A[i+1];
	A[n]=0;
	for(int i=0;i<3;i++) for(int j=0;j<3;j++) cs.dp[i][j]=-INF;
	cs.dp[0][0]=0;
	int lg=1,c=0;
	while(lg<n-1) lg*=2,c++;
	build(1,lg,1);
	while(q--)
	{
		int l,r,v;
		cin>>l>>r>>v;
		if(l!=1) update(l-1,-v);
		if(r!=n) update(r,v);
		cout<<get(1,n-1,c)<<"\n";
	}
}

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