QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429478#8179. 2D ParenthesesmaojunWA 176ms35472kbC++202.4kb2024-06-02 15:56:462024-06-02 15:56:47

Judging History

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

  • [2024-06-02 15:56:47]
  • 评测
  • 测评结果:WA
  • 用时:176ms
  • 内存:35472kb
  • [2024-06-02 15:56:46]
  • 提交

answer

#include<bits/stdc++.h>
#define mt make_tuple
using namespace std;

typedef unsigned long long ull;
const int N=4e5+5;
int n,x[N],y[N];
struct node{
	int x,y,p,o;node(){}
	node(int x,int y,int p,int o):x(x),y(y),p(p),o(o){}
	bool operator<(const node&b)const{return x^b.x?x<b.x:y<b.y;}
}a[N];
struct Q{
	int p,l,r,o;ull k;Q(){}
	Q(int p,int l,int r,int o,ull k):p(p),l(l),r(r),o(o),k(k){}
	bool operator<(const Q&b)const{
		if(p^b.p)return p<b.p;
		if(o^b.o)return o>b.o;
		return o^(r-l>b.r-b.l);
	}
}q[N];

const int S=N<<2;
ull val[S],tag[S];bool ok[S];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
#define Ls ls,l,mid
#define Rs rs,mid+1,r
#define all 1,1,V
inline void pu(int p){val[p]=val[ls];ok[p]=ok[ls]&&ok[rs]&&val[ls]==val[rs];}
inline void chg(int p,ull k){val[p]^=k;tag[p]^=k;}
inline void pd(int p){if(tag[p]){chg(ls,tag[p]);chg(rs,tag[p]);tag[p]=0;}}
void upd(int p,int l,int r,int L,int R,ull k){if(L<=l&&r<=R)return chg(p,k);pd(p);if(L<=mid)upd(Ls,L,R,k);if(R>mid)upd(Rs,L,R,k);}
ull lst;
bool qry(int p,int l,int r,int L,int R){if(L<=l&&r<=R){bool t=ok[p]&&(!~lst||lst==val[p]);lst=val[p];return t;}pd(p);return L>mid?qry(Rs,L,R):R<=mid?qry(Ls,L,R):qry(Ls,L,R)&&qry(Rs,L,R);}
mt19937 rnd(time(NULL));
int V=0,d[N];
int ans[N];
inline bool solve(){
	scanf("%d",&n);
	for(int i=1;i<=n+n;i++)scanf("%d%d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)a[i]=node(x[i],y[i],i,0);
	for(int i=1;i<=n;i++)a[n+i]=node(x[n+i],y[n+i],i,1);
	sort(a+1,a+n+n+1,[&](const node&a,const node&b){return mt(a.y,!a.o)<mt(b.y,!b.o);});
	set<node>s;
	for(int i=1;i<=n+n;i++)
		if(!a[i].o)s.insert(a[i]);
		else{
			if(s.empty())return false;
			auto it=s.lower_bound(node(a[i].x,a[i].y,a[i].p,a[i].o));
			if(it==s.begin())return false;
			ans[(--it)->p]=a[i].p;s.erase(it);
		}
	int m=0;
	for(int i=1;i<=n;i++){
		ull w=rnd();int j=n+ans[i];
		q[++m]=Q(x[i],y[i],y[j]-1,0,w);
		q[++m]=Q(x[j],y[i],y[j]-1,1,w);
		d[++V]=y[i];d[++V]=y[j]-1;
	}
	sort(d+1,d+V+1);V=unique(d+1,d+V+1)-d-1;
	sort(q+1,q+m+1);
	auto gn=[&](int x){return lower_bound(d+1,d+V+1,x)-d;};
	memset(ok,1,sizeof ok);
	for(int i=1;i<=m;i++){
		int l=gn(q[i].l),r=gn(q[i].r);
		lst=-1;if(!qry(all,l,r))return false;
		upd(all,l,r,q[i].k);
	}
	return true;
}
int main(){
	if(solve()){
		puts("Yes");
		for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	}else puts("No");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 14088kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 2ms
memory: 9860kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 176ms
memory: 35472kb

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