QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549434 | #8179. 2D Parentheses | NKheyuxiang | WA | 239ms | 49764kb | C++14 | 2.2kb | 2024-09-06 15:30:40 | 2024-09-06 15:30:40 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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