제출 #1313138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313138		boclobanchat	Feast (NOI19_feast)	C++20	22 / 100	70 ms	101232 KiB

feast

#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long sum,prefl,prefr,fsum;
	int posl,posr,fl,fr;
};
const int MAXN=3e5+5;
const int INF=1e9;
long long A[MAXN];
node merge1(node a,node b)
{
	node c;
	c.sum=a.sum+b.sum;
	if(a.prefl<a.sum+b.prefl) c.prefl=a.sum+b.prefl,c.posl=b.posl;
	else c.prefl=a.prefl,c.posl=a.posl;
	if(b.prefr<b.sum+a.prefr) c.prefr=b.sum+a.prefr,c.posr=a.posr;
	else c.prefr=b.prefr,c.posr=b.posr;
	if(a.fsum<b.fsum) c.fsum=b.fsum,c.fl=b.fl,c.fr=b.fr;
	else c.fsum=a.fsum,c.fl=a.fl,c.fr=a.fr;
	if(c.fsum<a.prefr+b.prefl) c.fsum=a.prefr+b.prefl,c.fl=a.posr,c.fr=b.posl;
	return c;
}
node merge2(node a,node b)
{
	node c;
	c.sum=a.sum+b.sum;
	if(a.prefl>a.sum+b.prefl) c.prefl=a.sum+b.prefl,c.posl=b.posl;
	else c.prefl=a.prefl,c.posl=a.posl;
	if(b.prefr>b.sum+a.prefr) c.prefr=b.sum+a.prefr,c.posr=a.posr;
	else c.prefr=b.prefr,c.posr=b.posr;
	if(a.fsum>b.fsum) c.fsum=b.fsum,c.fl=b.fl,c.fr=b.fr;
	else c.fsum=a.fsum,c.fl=a.fl,c.fr=a.fr;
	if(c.fsum>a.prefr+b.prefl) c.fsum=a.prefr+b.prefl,c.fl=a.posr,c.fr=b.posl;
	return c;
}
pair<node,node> seg[MAXN*4];
bool lazy[MAXN*4];
void flipnode(node& res)
{
	res={-res.sum,-res.prefl,-res.prefr,-res.fsum,res.posl,res.posr,res.fl,res.fr};
}
void flip(int pos)
{
	swap(seg[pos].first,seg[pos].second);
	flipnode(seg[pos].first);
	flipnode(seg[pos].second);
}
void down(int pos)
{
	if(lazy[pos])
	{
		flip(pos*2);
		flip(pos*2+1);
		lazy[pos*2]^=1,lazy[pos*2+1]^=1,lazy[pos]=0;
	}
}
void build(int l,int r,int pos)
{
	if(l==r)
	{
		seg[pos].first={A[l],max(0LL,A[l]),max(0LL,A[l]),max(0LL,A[l]),l,l,l,l};
		seg[pos].second={INF,0,0,0,l,l,l,l};
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,pos*2);
	build(mid+1,r,pos*2+1);
	seg[pos].first=merge1(seg[pos*2].first,seg[pos*2+1].first);
	seg[pos].second=merge2(seg[pos*2].second,seg[pos*2+1].second);
}
void update(int l,int r,int u,int v,int pos)
{
	if(v<l||r<u) return ;
	if(u<=l&&r<=v)
	{
		flip(pos);
		lazy[pos]^=1;
		return ;
	}
	int mid=(l+r)/2;
	down(pos);
	update(l,mid,u,v,pos*2);
	update(mid+1,r,u,v,pos*2+1);
	seg[pos].first=merge1(seg[pos*2].first,seg[pos*2+1].first);
	seg[pos].second=merge2(seg[pos*2].second,seg[pos*2+1].second);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	long long ans=0;
	for(int i=1;i<=n;i++) cin>>A[i];
	build(1,n,1);
	for(int i=1;i<=k;i++)
	{
		int l=seg[1].first.fl,r=seg[1].first.fr;
		int u=seg[1].second.fl,v=seg[1].second.fr;
		if(max(seg[1].first.fsum,seg[1].second.fsum)==0) break;
		if(seg[1].first.fsum>seg[1].second.fsum)
		{
			ans+=seg[1].first.fsum;
			update(1,n,l,r,1);
		}
		else
		{
			ans+=seg[1].second.fsum;
			update(1,n,u,v,1);
		}
	}
	cout<<ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29