QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#429624 | #8179. 2D Parentheses | maojun | WA | 119ms | 19684kb | C++20 | 2.4kb | 2024-06-02 18:24:58 | 2024-06-02 18:24:59 |
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 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]);
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,[&](const node&a,const node&b){return mt(a.y,!a.o,a.x)<mt(b.y,!b.o,b.x);});
set<node>s;
for(int i=1;i<=n+n;i++)
if(!a[i].o)s.insert(a[i]);
else{
if(s.empty())return false;
auto it=s.lower_bound(node(a[i].x,a[i].y,a[i].p,a[i].o));
if(it==s.begin())return false;
ans[(--it)->p]=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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 18240kb
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: 14028kb
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: 11908kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 119ms
memory: 19684kb
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 82079 143937 36911 23912 29196 103293 198434 65913 157367 48765 41010 148908 80650 146103 196489 99283 116023 160688 141927 99488 40423 87997 59175 165032 163355 57765 97472 31857 150106 185365 76890 97333 118296 142517 154996 163892 142018 1988 54877 191396 65560 70618 199137 56352 183975 16401...
result:
wrong answer 1st words differ - expected: '21701', found: '82079'