QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423281 | #8179. 2D Parentheses | lefy | WA | 310ms | 26724kb | C++14 | 2.5kb | 2024-05-27 22:04:11 | 2024-05-27 22:04:12 |
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 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--;
Ly[i]=a[i].y,a[i].id=i;
}
sort(Ly+1,Ly+1+n*2);
Y=unique(Ly+1,Ly+1+n*2)-Ly-1;
for(int i=1;i<=n*2;i++)a[i].y=lower_bound(Ly+1,Ly+1+Y,a[i].y)-Ly;
sort(a+1,a+n*2+1,cmp);
for(int i=1;i<=n*2;i++){
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;
}
// if(q(pos+1,a[i].y))cout<<"cnm\n";
// 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<<a[ans[a[i].id]].x<<" "<<" "<<a[ans[a[i].id]].y<<"\n";
// cout<<a[i].x<<" "<<a[i].y<<"\n";
}
if(n<100){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: 4ms
memory: 16120kb
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: 18088kb
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: 18092kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 310ms
memory: 26724kb
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 125911 24064 131376 24130 40012 70025 126129 65913 39416 14669 110521 49808 163083 111711 44237 109982 173973 92477 141927 161003 3329 98374 146130 110179 153382 78378 63476 163368 161659 22532 180060 22555 105965 192669 77221 4006 142534 85606 157007 60723 139898 143593 53129 6656 13162 91316 4...
result:
wrong answer 1st words differ - expected: '21701', found: '125911'