QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549434#8179. 2D ParenthesesNKheyuxiangWA 239ms49764kbC++142.2kb2024-09-06 15:30:402024-09-06 15:30:40

Judging History

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

  • [2024-09-06 15:30:40]
  • 评测
  • 测评结果:WA
  • 用时:239ms
  • 内存:49764kb
  • [2024-09-06 15:30:40]
  • 提交

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]);
	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: 3ms
memory: 37316kb

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

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

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 239ms
memory: 49764kb

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