QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#429642 | #8179. 2D Parentheses | maojun | WA | 189ms | 27664kb | C++20 | 2.3kb | 2024-06-02 18:45:35 | 2024-06-02 18:45:36 |
Judging History
answer
#include<bits/stdc++.h>
#define mt make_tuple
using namespace std;
typedef unsigned long long ull;
const int N=4e5+5;
int n,x[N],y[N];
struct node{
int x,y,p;node(){}
node(int x,int y,int p):x(x),y(y),p(p){}
bool operator<(const node&b)const{return x^b.x?x<b.x:y<b.y;}
}a[N];
struct Q{
int p,l,r,o;ull k;Q(){}
Q(int p,int l,int r,int o,ull k):p(p),l(l),r(r),o(o),k(k){}
bool operator<(const Q&b)const{
if(p^b.p)return p<b.p;
if(o^b.o)return o>b.o;
return o^(r-l>b.r-b.l);
}
}q[N];
const int S=N<<2;
ull val[S],tag[S];bool ok[S];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
#define Ls ls,l,mid
#define Rs rs,mid+1,r
#define all 1,1,V
inline void pu(int p){val[p]=val[ls];ok[p]=ok[ls]&&ok[rs]&&val[ls]==val[rs];}
inline void chg(int p,ull k){val[p]^=k;tag[p]^=k;}
inline void pd(int p){if(tag[p]){chg(ls,tag[p]);chg(rs,tag[p]);tag[p]=0;}}
void upd(int p,int l,int r,int L,int R,ull k){if(L<=l&&r<=R)return chg(p,k);pd(p);if(L<=mid)upd(Ls,L,R,k);if(R>mid)upd(Rs,L,R,k);pu(p);}
ull lst;
bool qry(int p,int l,int r,int L,int R){if(L<=l&&r<=R){!~lst&&(lst=val[p]);return ok[p]&&lst==val[p];}pd(p);return L>mid?qry(Rs,L,R):R<=mid?qry(Ls,L,R):qry(Ls,L,R)&&qry(Rs,L,R);}
mt19937_64 rnd(time(NULL));
int V=0,d[N];
int ans[N];
inline bool solve(){
scanf("%d",&n);
for(int i=1;i<=n+n;i++){scanf("%d%d",&x[i],&y[i]);a[i]=node(x[i],y[i],i);}
sort(a+1,a+n+n+1,[&](const node&a,const node&b){return mt(a.y,a.p<=n,a.x)<mt(b.y,b.p<=n,b.x);});
#define mp make_pair
set<pair<int,int>>s;
for(int i=1;i<=n+n;i++)
if(a[i].p<=n)s.insert(mp(a[i].x,a[i].p));
else{
if(s.empty())return false;
auto it=s.lower_bound(mp(a[i].x-1,n+n+1));
if(it==s.begin())return false;
ans[(--it)->second]=a[i].p;s.erase(it);
}
int m=0;
for(int i=1;i<=n;i++){
ull w=rnd();int j=ans[i];
q[++m]=Q(x[i],y[i],y[j]-1,0,w);
q[++m]=Q(x[j],y[i],y[j]-1,1,w);
d[++V]=y[i];d[++V]=y[j]-1;
}
sort(d+1,d+V+1);V=unique(d+1,d+V+1)-d-1;
sort(q+1,q+m+1);
auto gn=[&](int x){return lower_bound(d+1,d+V+1,x)-d;};
memset(ok,1,sizeof ok);
for(int i=1;i<=m;i++){
int l=gn(q[i].l),r=gn(q[i].r);
lst=-1;if(!qry(all,l,r))return false;
upd(all,l,r,q[i].k);
}
return true;
}
int main(){
if(solve()){
puts("Yes");
for(int i=1;i<=n;i++)printf("%d\n",ans[i]-n);
}else puts("No");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 16076kb
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: 13972kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 1ms
memory: 9904kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 189ms
memory: 27664kb
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