QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549465 | #8179. 2D Parentheses | NKheyuxiang | WA | 225ms | 50048kb | C++14 | 2.3kb | 2024-09-06 15:59:33 | 2024-09-06 15:59:34 |
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]);
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;
}
Details
Tip: Click on the bar to expand more detailed information
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