求助神秘 CE
  • 板块学术版
  • 楼主dxrS
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/9 21:42
  • 上次更新2024/9/9 21:49:17
查看原帖
求助神秘 CE
563958
dxrS楼主2024/9/9 21:42

系统是 Linux,软件是 VScode,PROBLEMS 里面无误,用了编译指令后 CE。

#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=2e5+5;
int n,sum,y[N],res[N],s[N],L,ans;
struct node{
	int val,l,r;
	node operator +(const node &o) const{ return node({val+o.val,l,o.r}); }
	friend bool operator <(node a,node b){ return a.val<b.val||(a.val&&a.l<b.l); }
};
struct ST{
	node lmax[2],rmax[2],ans[2],sum[2];
	bool tag;
	friend ST operator +(ST a,ST b){
		ST ans;
		ans.ans[0]=max({a.ans[0],b.ans[0],a.rmax[0]+b.lmax[0]});
		ans.lmax[0]=max(a.lmax[0],a.sum[0],b.lmax[0]);
		ans.rmax[0]=max(b.rmax[0],b.sum[0]+a.rmax[0]);
		ans.sum[0]=a.sum[0]+b.sum[0];
		ans.ans[1]=max({a.ans[1],b.ans[1],a.rmax[1]+b.lmax[1]});
		ans.lmax[1]=max(a.lmax[1],a.sum[1],b.lmax[1]);
		ans.rmax[1]=max(b.rmax[1],b.sum[1]+a.rmax[1]);
		ans.sum[1]=a.sum[1]+b.sum[1];
		return ans;
	}
}t[N<<2];
void update(int p){
	t[p].tag^=1;
	swap(t[p].ans[0],t[p].ans[1]);
	swap(t[p].lmax[0],t[p].lmax[1]);
	swap(t[p].rmax[0],t[p].rmax[1]);
	swap(t[p].sum[0],t[p].sum[1]);
}
void pushdown(int p){
	if(t[p].tag){
		update(ls),update(rs);
		t[p].tag=0;
	}
}
void build(int p,int l,int r){
	if(l==r){
		t[p].lmax[0]=t[p].rmax[0]=t[p].sum[0]=t[p].ans[0]=node({y[l],l,l});
		t[p].lmax[1]=t[p].rmax[1]=t[p].sum[1]=t[p].ans[1]=node({-y[l],l,l});
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	t[p]=t[ls]+t[rs];
}
void update(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		update(p);
		return;
	}
	pushdown(p);
	int mid=l+r>>1;
	if(ql<=mid) update(ls,l,mid,ql,qr);
	if(mid<qr) update(rs,mid+1,r,ql,qr);
	t[p]=t[ls]+t[rs];
}
signed main(){
	// freopen("hollow.in","r",stdin);
	// freopen("hollow.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n,L=n+1;
	for(int i=1,x;i<=n;++i){
		cin>>x>>y[i];
		if(x) sum+=y[i],y[i]=-y[i];
		res[i]=max(res[i-1],s[i]=s[i-1]+y[i]);
	}
	build(1,1,n);
	for(int i=0;i<=n;++i){
		cout<<res[L-1]+ans<<endl;
		ST res=t[1];
		if(res.ans[0].val>0){
			L=min(L,res.ans[0].l);
			ans+=res.ans[0].val;
			update(1,1,n,res.ans[0].l,res.ans[0].r);
		}
	}
	return 0;
}
2024/9/9 21:42
加载中...