QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429495#8179. 2D ParenthesesmaojunWA 131ms16736kbC++202.4kb2024-06-02 16:10:032024-06-02 16:10:04

Judging History

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

  • [2024-06-02 16:10:04]
  • 评测
  • 测评结果:WA
  • 用时:131ms
  • 内存:16736kb
  • [2024-06-02 16:10:03]
  • 提交

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 mt(y,!o)<mt(b.y,!b.o);}
}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);pu(p);}
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_64 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);
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
	set<pi>s;
	for(int i=1;i<=n+n;i++)
		if(!a[i].o)s.insert(mp(a[i].x,a[i].p));
		else{
			if(s.empty())return false;
			auto it=s.lower_bound(mp(a[i].x-1,n+n+1));
			if(it==s.begin())return false;
			ans[(--it)->se]=a[i].p;s.erase(it);
		}
	if(n>10)return true;
	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: 2ms
memory: 14440kb

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: 2ms
memory: 15992kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 1ms
memory: 10204kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 131ms
memory: 16736kb

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:

Yes
160239
162486
59327
52754
29196
103293
47114
198023
157367
48765
157321
148908
80650
112519
196489
109656
173973
5551
141927
136548
101692
182366
24748
165032
163355
93530
5843
31857
130090
155862
76890
97333
117762
85853
142718
4006
171963
1988
107334
29064
65560
70618
115785
151179
183975
1363...

result:

wrong answer 1st words differ - expected: '21701', found: '160239'