QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#429501 | #8179. 2D Parentheses | maojun | WA | 118ms | 19672kb | C++20 | 2.4kb | 2024-06-02 16:11:36 | 2024-06-02 16:11:37 |
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,o;node(){}
node(int x,int y,int p,int o):x(x),y(y),p(p),o(o){}
bool operator<(const node&b)const{return mt(y,!o,x)<mt(b.y,!b.o,b.x);}
}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){bool t=ok[p]&&(!~lst||lst==val[p]);lst=val[p];return t;}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]);
for(int i=1;i<=n;i++)a[i]=node(x[i],y[i],i,0);
for(int i=1;i<=n;i++)a[n+i]=node(x[n+i],y[n+i],i,1);
sort(a+1,a+n+n+1);
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
set<pi>s;
for(int i=1;i<=n+n;i++)
if(!a[i].o)s.insert(mp(a[i].x,a[i].p));
else{
if(s.empty())return false;
auto it=s.lower_bound(mp(a[i].x,0));
if(it==s.begin())return false;
ans[(--it)->se]=a[i].p;s.erase(it);
}
if(n>10)return true;
int m=0;
for(int i=1;i<=n;i++){
ull w=rnd();int j=n+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]);
}else puts("No");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14112kb
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: 2ms
memory: 13988kb
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: 10192kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 118ms
memory: 19672kb
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 21701 162486 59327 146960 29196 103293 136292 198023 157367 48765 157321 18491 80650 112519 196489 82724 173973 5551 141927 136548 101692 182366 24748 165032 163355 57765 5843 31857 130090 155862 76890 97333 97973 142517 142718 4006 27179 1988 107334 183071 65560 70618 199137 151179 183975 10185...
result:
wrong answer 2nd words differ - expected: '88398', found: '162486'