WA#6求调
查看原帖
WA#6求调
1043658
Purple_meteor楼主2024/4/7 17:17

好像是把一个有解判成无解了,求大佬看看

#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
string s[N];
int xx[N],yy[N],aa[N],totaa=-1,bb[N],totbb=-1;
int n,tot;
int maxn,la,lb;
set<int> ST[N];
struct lie
{
	int max,num;
}point[N];
struct tree
{
	int l,r,mid,x,y;
}t[N];
struct op
{
	char s;
	int x,y;
};
deque<op> dq;
void push_up(int p)
{
	t[p].y=max(t[p<<1].y,t[p<<1|1].y);
}
void build(int p,int l,int r)
{ 
	t[p].x=r;
	t[p].l=l;
	t[p].r=r;
	t[p].mid=(l+r)/2;
	if(l==r) return ;
	build(p<<1,l,t[p].mid);
	build(p<<1|1,t[p].mid+1,r);
}
void add(int x,int y,int p)
{
	if(t[p].l==t[p].r)
	{
		t[p].y=max(t[p].y,y);
		ST[x].insert(y);
		return ;
	}
	if(x<=t[p].mid) add(x,y,p<<1);
	else add(x,y,p<<1|1);
	push_up(p);
	return ;
}
void find(int x,int y,int p)
{
	if(t[p].l==t[p].r)
	{
		cout<<aa[t[p].x-1]<<' '<<bb[*ST[t[p].x].upper_bound(y)-1]<<'\n';
		return ;
	}
	if(x<t[p<<1].x&&y<t[p<<1].y) find(x,y,p<<1);
	else if(x<t[p<<1|1].x&&y<t[p<<1|1].y) find(x,y,p<<1|1);
	else cout<<-1<<endl;
	return ;
}
void remove(int x,int y,int p)
{
	if(t[p].l==t[p].r)
	{
		t[p].y=0;
		ST[x].erase(y);
		return ;
	}
	if(x<=t[p].mid) remove(x,y,p<<1);
	else remove(x,y,p<<1|1);
	push_up(p);
	return ;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>s[i];
		cin>>xx[i]>>yy[i];
		aa[++totaa]=xx[i];
		bb[++totbb]=yy[i];
	}
	sort(aa,aa+totaa+1);
	la=unique(aa,aa+totaa+1)-aa;
	maxn=la;
	sort(bb,bb+totbb+1);
	lb=unique(bb,bb+totbb+1)-bb;
	for(int i=1;i<=n;i++)
	{
		xx[i]=lower_bound(aa,aa+la,xx[i])-aa+1;
		yy[i]=lower_bound(bb,bb+lb,yy[i])-bb+1;
		point[xx[i]].max=max(point[xx[i]].max,yy[i]);
		if(s[i][0]!='r')
		{
			point[xx[i]].num++;
			if(s[i][0]=='a') ST[xx[i]].insert(yy[i]);
		}
		op c;
		c.s=s[i][0];
		c.x=xx[i];
		c.y=yy[i];
		dq.push_back(c);
	}
	build(1,1,maxn);
	while(!dq.empty())
	{
		op c=dq.front();
		dq.pop_front();
		switch(c.s)
		{
			case 'a':add(c.x,c.y,1);break;
			case 'r':remove(c.x,c.y,1);break;
			case 'f':find(c.x,c.y,1);
		}
	}
	return 0;
 } 
 ``````cpp
2024/4/7 17:17
加载中...