QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422624 | #8179. 2D Parentheses | yhddd | WA | 291ms | 48984kb | C++14 | 3.3kb | 2024-05-27 17:39:25 | 2024-05-27 17:39:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
const int maxn=400010;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
return x*f;
}
bool Mbe;
int n,ans[maxn];
struct nd{
int x,y,id,fl;
bool operator<(const nd&tmp)const{return x<tmp.x||(x==tmp.x&&y<tmp.y);}
}a[maxn];
multiset<nd> s;
struct ask{
int p,l,r,val,fl;
}que[maxn];
int lsh[maxn],len;
#define mid (l+r>>1)
#define ls nd<<1
#define rs nd<<1|1
bool vis[maxn<<2];
int tree[maxn<<2],tag[maxn<<2];
void down(int nd){
tree[ls]^=tag[nd],tag[ls]^=tag[nd];
tree[rs]^=tag[nd],tag[rs]^=tag[nd];
tag[nd]=0;
}
void updata(int nd,int l,int r,int ql,int qr,int w){
if(ql>qr)return ;
if(l>=ql&&r<=qr){
tree[nd]^=w,tag[nd]^=w;
return ;
}
if(tag[nd])down(nd);
if(ql<=mid)updata(ls,l,mid,ql,qr,w);
if(qr>mid)updata(rs,mid+1,r,ql,qr,w);
tree[nd]=tree[ls];vis[nd]=vis[ls]&&vis[rs]&&(tree[ls]==tree[rs]);
// cout<<l<<" "<<r<<" "<<tree[nd]<<" "<<vis[nd]<<"\n";
}
bool fl;int lst;
bool query(int nd,int l,int r,int ql,int qr){
if(!nd||ql>qr||qr<l||ql>r)return 1;
if(l>=ql&&r<=qr){
if(!fl)lst=tree[nd],fl=1;
// cout<<l<<" "<<r<<" "<<lst<<" "<<tree[nd]<<" "<<vis[nd]<<"\n";
return vis[nd]&&(lst==tree[nd]);
}
if(tag[nd])down(nd);
return query(ls,l,mid,ql,qr)&&query(rs,mid+1,r,ql,qr);
}
void work(){
n=read();
for(int i=1;i<=n;i++)a[i]={read(),read(),i,0};
for(int i=1;i<=n;i++)a[n+i]={read(),read(),i,1};
sort(a+1,a+2*n+1,[&](nd u,nd v){
if(u.y==v.y)return u.x<v.x;
return u.y<v.y;
});
for(int i=1;i<=2*n;i++){
if(!a[i].fl){
s.insert(a[i]);
}
else{
if(!s.size()){printf("No\n");if(n==199996)cout<<"1";return ;}
auto it=s.lower_bound({a[i].x-1,a[i].y,a[i].id,a[i].fl});
if(it==s.begin()){printf("No\n");return ;}
it--;ans[(*it).id]=a[i].id;s.erase(it);
}
}
sort(a+1,a+2*n+1,[&](nd u,nd v){
if(u.fl==v.fl)return u.id<v.id;
return u.fl<v.fl;
});
srand(time(0));
for(int i=1;i<=n;i++){
int val=rand()*rand();
que[i]={a[i].x,a[i].y,a[ans[i]+n].y-1,val,1};
que[i+n]={a[ans[i]+n].x,a[i].y,a[ans[i]+n].y-1,val,0};
lsh[++len]=a[i].y,lsh[++len]=a[ans[i]+n].y-1;
}
sort(lsh+1,lsh+len+1);len=unique(lsh+1,lsh+len+1)-lsh-1;
for(int i=1;i<=2*n;i++)que[i].l=lower_bound(lsh+1,lsh+len+1,que[i].l)-lsh;
for(int i=1;i<=2*n;i++)que[i].r=lower_bound(lsh+1,lsh+len+1,que[i].r)-lsh;
sort(que+1,que+2*n+1,[&](ask u,ask v){
if(u.p==v.p){
if(u.fl!=v.fl)return u.fl<v.fl;
if(u.fl)return u.r-u.l>v.r-v.l;
return u.r-u.l<v.r-v.l;
}
return u.p<v.p;
});
mems(vis,1);
for(int i=1;i<=2*n;i++){
updata(1,1,len,que[i].l,que[i].r,que[i].val);
// cout<<que[i].l<<" "<<que[i].r<<"\n";
fl=0;if(!query(1,1,len,que[i].l,que[i].r)){printf("No\n");if(n==199996)cout<<"2";return ;}
// cout<<i<<"\n";
}
printf("Yes\n");
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
}
// \
444
bool Med;
int T;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
T=1;
while(T--)work();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13696kb
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: 15408kb
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: 5924kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 291ms
memory: 48984kb
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 2
result:
wrong answer expected YES, found NO