QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464981#8179. 2D Parenthesesucup-team052WA 323ms44296kbC++145.0kb2024-07-06 16:36:062024-07-06 16:36:06

Judging History

你现在查看的是最新测评结果

  • [2024-07-06 16:36:06]
  • 评测
  • 测评结果:WA
  • 用时:323ms
  • 内存:44296kb
  • [2024-07-06 16:36:06]
  • 提交

answer

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
const int N=400005,INF=0X3F3F3F3F;
int n,ans[N];
vector<int>vx,vy;
struct node{
	int x,y,id;
}a[N];
struct cmp{
	bool operator()(const int&x,const int&y)const{
		if(a[x].x!=a[y].x)return a[x].x<a[y].x;
		if(a[x].y!=a[y].y)return a[x].y<a[y].y;
		return x<y;
	}
};
struct segtree{
	int mn[N<<2],sum[N<<2];
	void bud(int k1,int k2,int k3){
		mn[k1]=0;
		sum[k1]=0;
		if(k2==k3){
			return;
		}
		int mid=(k2+k3)>>1;
		bud(k1*2,k2,mid),bud(k1*2+1,mid+1,k3);
	}
	void upd(int k1){
		mn[k1]=min(mn[k1*2],sum[k1*2]+mn[k1*2+1]);
		sum[k1]=sum[k1*2]+sum[k1*2+1];
	}
	void init(){
		bud(1,1,SZ(vy));
	}
	void add(int k1,int k2,int k3,int k4,int k5){
		if(k2==k3){
			mn[k1]+=k5;
			sum[k1]+=k5;
			return;
		}
		int mid=(k2+k3)>>1;
		if(k4<=mid)add(k1*2,k2,mid,k4,k5);else add(k1*2+1,mid+1,k3,k4,k5);
		upd(k1);
	}
	void add(int x,int y){
		// D("add %d %d\n",x,y);
		add(1,1,SZ(vy),x,y);
	}
	int MN,SUM;
	void check(int k1,int k2,int k3,int k4,int k5){
		if(k2>k5||k3<k4)return;
		if(k4<=k2&&k3<=k5){
			MN=min(MN,SUM+mn[k1]);
			SUM+=sum[k1];
			return;
		}
		int mid=(k2+k3)>>1;
		check(k1*2,k2,mid,k4,k5);
		check(k1*2+1,mid+1,k3,k4,k5);
	}
	bool check(int l,int r){
		// D("check %d %d\n",l,r);
		MN=0,SUM=0;
		check(1,1,SZ(vy),l,r);
		return MN==0;
	}
}sgt;
struct segtree2{
	int mx[N<<2];
	void bud(int k1,int k2,int k3){
		mx[k1]=0;
		if(k2==k3){
			return;
		}
		int mid=(k2+k3)>>1;
		bud(k1*2,k2,mid),bud(k1*2+1,mid+1,k3);
	}
	void init(){
		bud(1,1,SZ(vy));
	}
	void upd(int k1){
		mx[k1]=max(mx[k1*2],mx[k1*2+1]);
	}
	void umax(int k1,int k2,int k3,int k4,int k5){
		if(k2==k3){
			mx[k1]=max(mx[k1],k5);
			return;
		}
		int mid=(k2+k3)>>1;
		if(k4<=mid)umax(k1*2,k2,mid,k4,k5);
		else umax(k1*2+1,mid+1,k3,k4,k5);
		upd(k1);
	}
	int MX;
	void qmax(int k1,int k2,int k3,int k4,int k5){
		if(k2>k5||k3<k4)return;
		if(k4<=k2&&k3<=k5){
			MX=max(MX,mx[k1]);
			return;
		}
		int mid=(k2+k3)>>1;
		qmax(k1*2,k2,mid,k4,k5);
		qmax(k1*2+1,mid+1,k3,k4,k5);
	}
	void umax(int x,int y){
		umax(1,1,SZ(vy),x,y);
	}
	int qmax(int l,int r){
		MX=0;
		if(l<=r)qmax(1,1,SZ(vy),l,r);
		return MX;
	}
	
}sgt2;
vector<tuple<int,int,int,int> >vec[N];
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(n);
	rep(i,1,n){
		rd(a[i].x),rd(a[i].y),a[i].id=i;
	}
	rep(i,n+1,n+n){
		rd(a[i].x),rd(a[i].y),a[i].id=i;
	}
	rep(i,1,n+n)vx.pb(a[i].x),vy.pb(a[i].y);
	sort(vx.begin(),vx.end()),vx.erase(unique(vx.begin(),vx.end()),vx.end());
	sort(vy.begin(),vy.end()),vy.erase(unique(vy.begin(),vy.end()),vy.end());
	rep(i,1,n+n){
		a[i].x=lower_bound(vx.begin(),vx.end(),a[i].x)-vx.begin()+1;
		a[i].y=lower_bound(vy.begin(),vy.end(),a[i].y)-vy.begin()+1;
	}
	sort(a+1,a+n+n+1,[&](node u,node v){return u.y!=v.y?u.y<v.y:u.x<v.x;});
	set<int,cmp>S;
	for(int i=1,j;i<=n+n;i=j){
		j=i+1;
		while(j<=n+n&&a[i].y==a[j].y)++j;
		rep(k,i,j-1)if(a[k].id>n){
			a[0].x=a[k].x;
			a[0].y=~INF;
			auto it=S.lower_bound(0);
			if(it!=S.begin()){
				--it;
				node u=a[*it];
				ans[u.id]=a[k].id-n;
				S.erase(it);
			}else{
				puts("No");
				exit(0);
			}
		}
		rep(k,i,j-1)if(a[k].id<=n){
			S.insert(k);
		}
	}
	sort(a+1,a+n+n+1,[&](node lhs,node rhs){return lhs.id<rhs.id;});
	auto check=[&](){
		rep(i,1,n+n)vec[i].clear();
		rep(i,1,n){
			vec[a[i].x].eb(a[i].y,a[ans[i]+n].y,1,a[ans[i]+n].x);
			vec[a[ans[i]+n].x].eb(a[i].y,a[ans[i]+n].y,-1,0);
		}
		sgt.init();
		sgt2.init();
		rep(x,1,SZ(vx)){
			for(auto&u:vec[x]){
				if(get<2>(u)==-1){
					if(sgt2.qmax(get<0>(u)+1,get<1>(u)-1)>x){
						puts("No");
						exit(0);
					}
				}
			}
			for(auto&u:vec[x]){
				if(get<2>(u)==1){
					sgt.add(get<0>(u),1);
					sgt.add(get<1>(u),-1);
					sgt2.umax(get<0>(u),get<3>(u));
					sgt2.umax(get<1>(u),get<3>(u));
				}else{
					sgt.add(get<0>(u),-1);
					sgt.add(get<1>(u),1);
				}
			}
			for(auto&u:vec[x]){
				if(get<2>(u)==1){
					if(!sgt.check(get<0>(u),get<1>(u)-1)){
						puts("No");
						exit(0);
					}
				}
			}
		}
	};
	check();
	rep(i,1,n+n){
		swap(a[i].x,a[i].y);
	}
	swap(vx,vy);
	check();
	puts("Yes");
	rep(i,1,n)printf("%d\n",ans[i]);
	return 0;
}

/*
......
......
..5...
2..46.
..3...
.1....

*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 22956kb

input:

3
0 0
2 -2
1 1
2 2
3 1
2 3

output:

Yes
3
2
1

result:

ok answer is YES, 3 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 22836kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 5ms
memory: 18524kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 323ms
memory: 44296kb

input:

199996
94702923 895749121
-830347683 823853414
-638337012 -528381915
774504965 -903560893
465975432 931026841
47062323 901390864
539345338 830099354
278774201 896803047
-445303873 568413124
80473317 828648317
804283391 -307873779
543648687 893783688
814084625 -664894626
169476937 -999435847
-8232728...

output:

No

result:

wrong answer expected YES, found NO