Submission #1313139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313139		boclobanchat	Feast (NOI19_feast)	C++20	22 / 100	69 ms	101240 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 merge(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=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.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