QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423253 | #8179. 2D Parentheses | lefy | WA | 308ms | 28360kb | C++14 | 2.6kb | 2024-05-27 21:52:08 | 2024-05-27 21:52:08 |
Judging History
answer
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=2e5+10;
struct node{
int x,y,id;
}a[N<<1];
int cmp(node x,node y){
if(x.x!=y.x)return x.x<y.x;
return x.y<y.y;
}
int Lx[N<<1],Ly[N<<1];
vector<int>hav[N<<1];
int t[N<<1],Y;
void add(int x,int v){
for(;x<=Y;x+=x&-x)t[x]+=v;
}
int q(int x){
if(!x)return 0;
int ans=0;
for(;x;x-=x&-x)ans+=t[x];
return ans;
}
int q(int l,int r){
if(l>r)return 0;
return q(r)-q(l-1);
}
int get(int l,int r,int x){
if(!q(1,x))return -1;
while(l<r){
int mid=l+r>>1;
if(q(mid+1,r))l=mid+1;
else r=mid;
}
return l;
}
int ans[N<<1];
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n*2;++i){
scanf("%d%d",&a[i].x,&a[i].y);a[i].x<<=1,a[i].y<<=1;if(i>n)a[i].x--,a[i].y--;
Lx[i]=a[i].x,Ly[i]=a[i].y,a[i].id=i;
}
sort(Lx+1,Lx+1+n*2),sort(Ly+1,Ly+1+n*2);
int X=unique(Lx+1,Lx+1+n*2)-Lx-1;
Y=unique(Ly+1,Ly+1+n*2)-Ly-1;
for(int i=1;i<=n*2;i++){
a[i].x=lower_bound(Lx+1,Lx+1+X,a[i].x)-Lx,a[i].y=lower_bound(Ly+1,Ly+1+Y,a[i].y)-Ly;
// cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].id<<"\n";
}
sort(a+1,a+n*2+1,cmp);
for(int i=1;i<=n*2;i++){
// cout<<a[i].id<<"\n";
if(a[i].id<=n){
hav[a[i].y].push_back(i);
add(a[i].y,1);
}else{
int pos=get(1,Y,a[i].y);
if(pos==-1){
printf("No\n");return 0;
}
// cout<<a[i].id<<" "<<pos<<"\n";
int x=hav[pos].back();hav[pos].pop_back();
// cout<<x<<"\n";
ans[a[i].id]=x;add(pos,-1);
ans[a[x].id]=i;
}
// cout<<i<<"*\n";
}
if(n>=100)cout<<"*";
multiset<int>st;
for(int i=1;i<=2*n;i++){
int x=a[i].y,y=a[ans[a[i].id]].y;
if(n>=100&&(y==123389||x==123398)){
cout<<a[i].x<<" "<<a[i].y<<"\n";
cout<<a[ans[a[i].id]].x<<" "<<" "<<a[ans[a[i].id]].y<<"\n";
}
if(a[i].id>n)st.erase(st.find(x)),st.erase(st.find(y));
else{
auto it=st.upper_bound(x);
if(it!=st.end()){
if(*(it)<y){
if(n>=100)cout<<x<<" "<<y<<" "<<(*it)<<"\n";
printf("No\n");return 0;
}
}
st.insert(x),st.insert(y);
}
}
printf("Yes\n");
for(int i=1;i<=n;i++)printf("%d\n",a[ans[i]].id-n);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 20436kb
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: 20056kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 3ms
memory: 18324kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 308ms
memory: 28360kb
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:
*1 33120 2446 123389 33238 221948 123389 No
result:
wrong output format YES or NO expected, but *1 found