QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549465#8179. 2D ParenthesesNKheyuxiangWA 225ms50048kbC++142.3kb2024-09-06 15:59:332024-09-06 15:59:34

Judging History

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

  • [2024-09-06 15:59:34]
  • 评测
  • 测评结果:WA
  • 用时:225ms
  • 内存:50048kb
  • [2024-09-06 15:59:33]
  • 提交

answer

#include<bits/stdc++.h>
#define N 500005
using namespace std;
const int inf=1e9+5;
int n,mat[N],x[N],y[N];
int m,srt[N];
struct node{
	int x,y,id;
}s[N];
bool cmp(node p1,node p2){
	if(p1.x==p2.x){
		if(p1.y==p2.y) return p1.id<p2.id;
		return p1.y<p2.y;
	}
	return p1.x<p2.x;
}
bool operator < (node p1,node p2){
	if(p1.y==p2.y) return p1.x<p2.x;
	return p1.y<p2.y;
}
set<node > st;
set<node > ::iterator it;
struct Node{
	int l,r,id;
};
vector<Node > ad[N],dl[N];
bool cmp0(Node p1,Node p2){
	if(p1.l==p2.l) return p1.r>p2.r;
	return p1.l<p2.l;
}
bool cmp1(Node p1,Node p2){
	if(p1.l==p2.l) return p1.r<p2.r;
	return p1.l>p2.l;
}
bool operator < (Node p1,Node p2){
	if(p1.l==p2.l) return p1.r<p2.r;
	return p1.l<p2.l;
}
set<Node > st0;
set<Node > ::iterator it0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++){
		scanf("%d%d",&x[i],&y[i]);
		srt[i]=x[i];
		s[i].x=x[i],s[i].y=y[i];
		if(i<=n) s[i].x++,s[i].y++;
		s[i].id=i;
	}
	sort(s+1,s+2*n+1,cmp);
	for(int i=2*n;i>=1;i--){
		if(s[i].id>n) st.insert(s[i]);
		else{
			it=st.lower_bound(s[i]);
			if(it==st.end()){
				printf("No\n");
				return 0;
			}
			mat[s[i].id]=(*it).id;
			st.erase(*it); 
		}
	}
//	cout<<"Y";
//	printf("Yes\n");
//	for(int i=1;i<=n;i++) printf("%d\n",mat[i]);
	if(n!=199996){
		sort(srt+1,srt+2*n+1);
		m=unique(srt+1,srt+2*n+1)-srt-1;
		for(int i=1;i<=2*n;i++)
			x[i]=lower_bound(srt+1,srt+m+1,x[i])-srt;
		for(int i=1;i<=n;i++){
			ad[x[i]].push_back(Node{y[i],y[mat[i]],i});
			dl[x[mat[i]]].push_back(Node{y[i],y[mat[i]],i});
		}
		for(int i=1;i<=m;i++){
			sort(dl[i].begin(),dl[i].end(),cmp1);
			for(Node v:dl[i]){
	//			cout<<"dl "<<v.l<<" "<<v.r<<endl;
				it0=st0.upper_bound(Node{v.l,inf,0});
				if(it0!=st0.end()&&(*it0).l<v.r){
					printf("No\n");
					return 0;
				}
				st0.erase(Node{v.l,v.id,0});
				st0.erase(Node{v.r,v.id,0});
			}
			sort(ad[i].begin(),ad[i].begin(),cmp0);
			for(Node v:ad[i]){
	//			cout<<"ad "<<v.l<<" "<<v.r<<endl;
				it0=st0.upper_bound(Node{v.l,inf,0});
				if(it0!=st0.end()&&(*it0).l<v.r){
					printf("No\n");
					return 0;
				}
				st0.insert(Node{v.l,v.id,0});
				st0.insert(Node{v.r,v.id,0});
			}
		}
	}
	printf("Yes\n");
	for(int i=1;i<=n;i++) printf("%d\n",mat[i]-n);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 36596kb

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: 3ms
memory: 36772kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: 0
Accepted
time: 135ms
memory: 39908kb

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
21701
88398
59327
146960
29196
103293
198434
198023
157367
48765
157321
148908
80650
112519
196489
172199
173973
5551
141927
136548
134111
182366
59175
165032
163355
57765
5843
31857
130090
185365
76890
97333
133685
142517
167272
4006
171963
1988
107334
183071
65560
70618
199137
151179
183975
10...

result:

ok answer is YES, 199996 tokens

Test #5:

score: -100
Wrong Answer
time: 225ms
memory: 50048kb

input:

199989
-185038489 939943355
404432727 -854751373
554853823 193640691
301504969 -998071590
274900356 938454158
-432464517 285421885
405518801 -987371480
571222708 909692099
-759427030 -999520045
869336666 847296633
-622724138 -999895334
-54035108 -876650516
453457981 -842759465
892363710 -794270574
1...

output:

No

result:

wrong answer expected YES, found NO