关于判断 Peace
查看原帖
关于判断 Peace
376997
Harry27182SDream楼主2022/7/17 16:55

我一开始写的判断 Peace 不对,一直 WA 50pts,然后后来按照题解写的改成了注释掉的这行就过了,请问这是为什么

#include<bits/stdc++.h>
using namespace std;
int q,maxn,num,b[2000005],tree[2000005][2],c[2000005];
struct node
{
	int op,t,x,y;
}a[2000005];
void change(int x,int y,int op)
{
	for(int i=x;i<=maxn;i+=i&(-i))tree[i][op]+=y;
}
int query(int x,int op)
{
	int res=0;
	for(int i=x;i;i-=i&(-i))res+=tree[i][op];
	return res;
}
int main()
{
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d",&a[i].op);
		if(a[i].op==1)
		{
			scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);
			b[++num]=a[i].x;
		}
		else scanf("%d",&a[i].t);
	}
	sort(b+1,b+num+1);
	int len=unique(b+1,b+num+1)-b-1,sum=0;
	for(int i=1;i<=q;i++)
	{
		if(a[i].op==1)
		{
			int now=a[i].x;
			a[i].x=lower_bound(b+1,b+len+1,a[i].x)-b;
			c[a[i].x]=now;
			maxn=max(maxn,a[i].x);
		}
	}
	for(int i=1;i<=q;i++)
	{
		if(a[i].op==1)
		{
			if(a[i].t==0)change(a[i].x,a[i].y,0);
			else change(a[i].x+1,a[i].y,1),sum+=a[i].y;
		}
		else 
		{
			if(a[a[i].t].t==0)change(a[a[i].t].x,-a[a[i].t].y,0);
			else change(a[a[i].t].x+1,-a[a[i].t].y,1),sum-=a[a[i].t].y;
		}
		int tmp1=0,tmp2=sum,now=0;
		for(int j=21;j>=0;j--)
		{
			if(now+(1<<j)>maxn)continue;
			if(tmp1+tree[now+(1<<j)][0]<tmp2-tree[now+(1<<j)][1])
			{
				tmp1+=tree[now+(1<<j)][0];
				tmp2-=tree[now+(1<<j)][1];
				now+=(1<<j);
			}
		}
		int ans1=tmp1,ans2=sum-query(now+1,1);
		//if((!ans1&&!ans2)||query(now+1,0)<ans2){printf("Peace\n");continue;}
		if(ans1>ans2)
		{
			printf("%d %d\n",c[now],ans1<<1);
			continue;
		}
		tmp1=0;tmp2=sum;now=0;
		for(int j=21;j>=0;j--)
		{
			if(now+(1<<j)>maxn)continue;
			if(tmp1+tree[now+(1<<j)][0]<tmp2-tree[now+(1<<j)][1]||
			tmp2-tree[now+(1<<j)][1]==ans2)
			{
				tmp1+=tree[now+(1<<j)][0];
				tmp2-=tree[now+(1<<j)][1];
				now+=(1<<j);
			}
		}
		printf("%d %d\n",c[now],ans2<<1);
	}
	return 0;
}
2022/7/17 16:55
加载中...