QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423290 | #8179. 2D Parentheses | lefy | WA | 241ms | 41444kb | C++14 | 2.1kb | 2024-05-27 22:06:13 | 2024-05-27 22:06:14 |
Judging History
answer
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=4e5+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(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){
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: 3ms
memory: 28392kb
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: 28284kb
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: 28368kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 241ms
memory: 41444kb
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