제출 #447824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447824		Jasiekstrz	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	1004 ms	50076 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int PP=3e5;
const int INF=1e9+7;
struct Dc
{
	long long t[3][3]; // -,0,+
	long long* operator[](int x)
	{
		return t[x];
	}
	void operator+=(long long c)
	{
		for(int i=0;i<3;i++)
		{
			t[0][i]-=c;
			t[i][0]-=c;
			t[2][i]+=c;
			t[i][2]+=c;
		}
		return;
	}
	void init(int c)
	{
		for(int i=0;i<3;i++)
		{
			for(int j=0;j<3;j++)
				t[i][j]=-INF;
		}
		t[0][1]=t[1][0]=-c;
		t[1][1]=0;
		t[2][1]=t[1][2]=c;
		return;
	}
};
Dc operator+(Dc &a,Dc &b)
{
	Dc ans;
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			ans[i][j]=max(a[i][j],b[i][j]);
			for(int k=0;k<3;k++)
				ans[i][j]=max(ans[i][j],a[i][k]+b[3-k-1][j]);
		}
	}
	return ans;
}
int pot;
Dc tree[2*PP+10];
long long lazy[2*PP+10];
void propagate(int i)
{
	if(lazy[i]==0)
		return;
	tree[2*i]+=lazy[i];
	tree[2*i+1]+=lazy[i];
	lazy[2*i]+=lazy[i];
	lazy[2*i+1]+=lazy[i];
	lazy[i]=0;
	return;
}
void add(int i,int l,int r,int ls,int rs,long long c)
{
	if(r<ls || rs<l)
		return;
	if(ls<=l && r<=rs)
	{
		tree[i]+=c;
		lazy[i]+=c;
		return;
	}
	propagate(i);
	int mid=(l+r)/2;
	add(2*i,l,mid,ls,rs,c);
	add(2*i+1,mid+1,r,ls,rs,c);
	tree[i]=tree[2*i]+tree[2*i+1];
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		tree[pot+i-1].init(x);
	}
	for(int i=pot+n;i<2*pot;i++)
		tree[i]=tree[i-1];
	for(int i=pot-1;i>=1;i--)
		tree[i]=tree[2*i]+tree[2*i+1];
	while(q--)
	{
		int l,r,c;
		cin>>l>>r>>c;
		if(r==n)
			r=pot;
		add(1,1,pot,l,r,c);
		cout<<tree[1][1][1]<<"\n";
	}
	return 0;
}

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