QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422790 | #8179. 2D Parentheses | msk_sama | WA | 57ms | 15916kb | C++14 | 4.8kb | 2024-05-27 19:20:55 | 2024-05-27 19:20:56 |
Judging History
answer
#include <bits/stdc++.h>
#define MISAKA main
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
const int N=2e5+10,inf=1e9,mod=998244353;
struct point{int x,y,id;}p1[N],p2[N];
struct line{int h,l,r,tp;ull v;}a[N];
struct Node{int ls,rs,mx;}t[N<<6];
int n,K=0,cnt=0,_cnt=0,root=0,_root=0,ans[N];
int mmax(int a,int b){return p1[a].x>p1[b].x?a:b;}
void update(int &now,ll L,ll R,int x,int id){
// cerr<<L<<' '<<R<<' '<<x<<' '<<id<<endl;
if(!now) now=++cnt;ll mid=L+R>>1;
if(L==R){t[now].mx=id;return;}
if(x<=mid) update(t[now].ls,L,mid,x,id);
else update(t[now].rs,mid+1,R,x,id);
t[now].mx=mmax(t[t[now].ls].mx,t[t[now].rs].mx);
}
int query(int now,ll L,ll R,int l,int r){
if(L>r||R<l||!now) return 0;ll mid=L+R>>1;
if(l<=L&&R<=r) return t[now].mx;
return mmax(query(t[now].ls,L,mid,l,r),query(t[now].rs,mid+1,R,l,r));
}
bool cmp(point a,point b){return a.y!=b.y?a.y<b.y:a.x>b.x;}
bool _cmp(line a,line b){return a.h!=b.h?a.h<b.h:a.tp<b.tp;}
ull rd(){return (ull)(-rand())^(ull)rand()*rand()^34621273340549655943ull;}
struct node{int ls,rs,tag;ull val,lazy;}tn[N<<6];
// void upd(int &now,ll L,ll R,int x,ull k){
// if(!now) now=++_cnt;ll mid=L+R>>1;
// if(L==R){tn[now].sum+=k;return;}
// if(x<=mid) upd(tn[now].ls,L,mid,x,k);
// else upd(tn[now].rs,mid+1,R,x,k);
// tn[now].sum=tn[tn[now].ls].sum+tn[tn[now].rs].sum;
// }
// ull qry(int now,ll L,ll R,int l,int r){
// if(L>r||R<l||!now||l>r) return 0;ll mid=L+R>>1;
// if(l<=L&&R<=r) return tn[now].sum;
// return qry(tn[now].ls,L,mid,l,r)+qry(tn[now].rs,mid+1,R,l,r);
// }
void pushup(int now){
tn[now].tag=tn[tn[now].ls].tag&&tn[tn[now].rs].tag&&tn[tn[now].ls].val==tn[tn[now].rs].val;
tn[now].val=tn[tn[now].ls].val;
}
void New(int &now){now=++_cnt,tn[now].tag=1;}
void cal(int now,ull x){tn[now].val^=x,tn[now].lazy^=x;}
void pushdown(int now){
if(!tn[now].lazy) return;
if(!tn[now].ls) New(tn[now].ls);
if(!tn[now].rs) New(tn[now].rs);
cal(tn[now].ls,tn[now].lazy);
cal(tn[now].rs,tn[now].lazy);
tn[now].lazy=0;
}
void upd(int &now,ll L,ll R,int l,int r,ull x){
if(!now) New(now);if(l>r||L>r||R<l) return;
if(l<=L&&R<=r) return cal(now,x);
pushdown(now);int mid=L+R>>1;
upd(tn[now].ls,L,mid,l,r,x);upd(tn[now].rs,mid+1,R,l,r,x);
pushup(now);
}
node qry(int now,ll L,ll R,int l,int r){
if(L>r||R<l) return node{0,0,1,0,0};
if(l<=L&&R<=r) return tn[now];
pushdown(now);int mid=L+R>>1;
if(r<=mid) return qry(tn[now].ls,L,mid,l,r);
if(l>mid) return qry(tn[now].rs,mid+1,R,l,r);
node a=qry(tn[now].ls,L,mid,l,r),b=qry(tn[now].rs,mid+1,R,l,r);
node res;res.tag=a.tag&&b.tag&&a.val==b.val;res.val=a.val;
return res;
}
signed MISAKA(){
srand(time(0));
n=read();p1[0].x=-2ll*inf;t[0].mx=0;tn[0].tag=1;
for(int i=1;i<=n;i++) p1[i].x=read(),p1[i].y=read(),p1[i].id=i;
for(int i=1;i<=n;i++) p2[i].x=read(),p2[i].y=read(),p2[i].id=i;
sort(p1+1,p1+n+1,cmp);sort(p2+1,p2+n+1,cmp);
for(int i=1,p=0;i<=n;i++){
while(p<n&&p1[p+1].y<p2[i].y){
p++;
// cout<<p1[p].x+inf<<endl;
update(root,0,2ll*inf,p1[p].x+inf,p);
}
// cerr<<i<<' '<<p<<' '<<t[root].mx<<endl;
int id=query(root,0,2ll*inf,0,p2[i].x-1+inf);
if(!id){printf("No");return 0;}
update(root,0,2ll*inf,p1[id].x+inf,0);
ull val=rd();ans[p1[id].id]=p2[i].id;
a[++K]=line{p1[id].y,p1[id].x,p2[i].x,1,val};
a[++K]=line{p2[i].y,p1[id].x,p2[i].x,-1,val};
// cerr<<p1[id].x<<' '<<p1[id].y<<' '<<p2[i].x<<' '<<p2[i].y<<endl;
}
// upd(_root,0,2*inf,1,3,4);
// upd(_root,0,2*inf,2,5,11);
// node t=qry(_root,0,2*inf,1,5);
// cout<<t.tag;
sort(a+1,a+K+1,_cmp);
for(int i=1;i<=K;i++){
// if(a[i].tp==-1){
// // if(qry(_root,0,2*inf,a[i].l+inf,a[i].r-1+inf)){printf("No");return 0;}
// // upd(_root,0,2ll*inf,a[i].l+inf,-a[i].v);
// // upd(_root,0,2ll*inf,a[i].r+inf,a[i].v);
// }else{
// if(qry(_root,0,2*inf,a[i].l+inf,a[i].r-1+inf)){printf("No");return 0;}
// upd(_root,0,2ll*inf,a[i].l+inf,a[i].v);
// upd(_root,0,2ll*inf,a[i].r+inf,-a[i].v);
// }
if(a[i].tp==1){
node t=qry(_root,0,2*inf,a[i].l+inf,a[i].r+inf-1);
if(!t.tag){printf("No");return 0;}
}
upd(_root,0,2*inf,a[i].l+inf,a[i].r+inf-1,a[i].v);
}
printf("Yes\n");
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12176kb
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: 11972kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 2ms
memory: 9996kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 57ms
memory: 15916kb
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