Submission #1313146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313146		boclobanchat	Feast (NOI19_feast)	C++20	100 / 100	257 ms	201548 KiB

feast

#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long sum,prefl,prefr,fsum;
	int posl,posr,fl,fr;
};
struct pnode
{
	node mx,mn;
};
const int MAXN=3e5+5;
const int INF=1e9;
long long A[MAXN];
pnode merge(pnode a,pnode b)
{
	pnode c;
	c.mx.sum=a.mx.sum+b.mx.sum;
	if(a.mx.prefl<a.mx.sum+b.mx.prefl) c.mx.prefl=a.mx.sum+b.mx.prefl,c.mx.posl=b.mx.posl;
	else c.mx.prefl=a.mx.prefl,c.mx.posl=a.mx.posl;
	if(b.mx.prefr<b.mx.sum+a.mx.prefr) c.mx.prefr=b.mx.sum+a.mx.prefr,c.mx.posr=a.mx.posr;
	else c.mx.prefr=b.mx.prefr,c.mx.posr=b.mx.posr;
	if(a.mx.fsum<b.mx.fsum) c.mx.fsum=b.mx.fsum,c.mx.fl=b.mx.fl,c.mx.fr=b.mx.fr;
	else c.mx.fsum=a.mx.fsum,c.mx.fl=a.mx.fl,c.mx.fr=a.mx.fr;
	if(c.mx.fsum<a.mx.prefr+b.mx.prefl) c.mx.fsum=a.mx.prefr+b.mx.prefl,c.mx.fl=a.mx.posr,c.mx.fr=b.mx.posl;
	c.mn.sum=a.mn.sum+b.mn.sum;
	if(a.mn.prefl>a.mn.sum+b.mn.prefl) c.mn.prefl=a.mn.sum+b.mn.prefl,c.mn.posl=b.mn.posl;
	else c.mn.prefl=a.mn.prefl,c.mn.posl=a.mn.posl;
	if(b.mn.prefr>b.mn.sum+a.mn.prefr) c.mn.prefr=b.mn.sum+a.mn.prefr,c.mn.posr=a.mn.posr;
	else c.mn.prefr=b.mn.prefr,c.mn.posr=b.mn.posr;
	if(a.mn.fsum>b.mn.fsum) c.mn.fsum=b.mn.fsum,c.mn.fl=b.mn.fl,c.mn.fr=b.mn.fr;
	else c.mn.fsum=a.mn.fsum,c.mn.fl=a.mn.fl,c.mn.fr=a.mn.fr;
	if(c.mn.fsum>a.mn.prefr+b.mn.prefl) c.mn.fsum=a.mn.prefr+b.mn.prefl,c.mn.fl=a.mn.posr,c.mn.fr=b.mn.posl;
	return c;
}
pair<pnode,pnode> seg[MAXN*4];
bool lazy[MAXN*4];
void flipnode(pnode& res)
{
	swap(res.mn,res.mx);
	res.mx={-res.mx.sum,-res.mx.prefl,-res.mx.prefr,-res.mx.fsum,res.mx.posl,res.mx.posr,res.mx.fl,res.mx.fr};
	res.mn={-res.mn.sum,-res.mn.prefl,-res.mn.prefr,-res.mn.fsum,res.mn.posl,res.mn.posr,res.mn.fl,res.mn.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.mx={A[l],max(0LL,A[l]),max(0LL,A[l]),max(0LL,A[l]),l,l,l,l};
		seg[pos].first.mn={A[l],min(0LL,A[l]),min(0LL,A[l]),min(0LL,A[l]),l,l,l,l};
		seg[pos].second.mx={0,0,0,0,l,l,l,l};
		seg[pos].second.mn={0,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=merge(seg[pos*2].first,seg[pos*2+1].first);
	seg[pos].second=merge(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=merge(seg[pos*2].first,seg[pos*2+1].first);
	seg[pos].second=merge(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.mx.fl,r=seg[1].first.mx.fr;
		int u=seg[1].second.mx.fl,v=seg[1].second.mx.fr;
		if(max(seg[1].first.mx.fsum,seg[1].second.mx.fsum)==0) break;
		if(seg[1].first.mx.fsum>seg[1].second.mx.fsum)
		{
			ans+=seg[1].first.mx.fsum;
			update(1,n,l,r,1);
		}
		else
		{
			ans+=seg[1].second.mx.fsum;
			update(1,n,u,v,1);
		}
	}
	cout<<ans;
}

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