QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#429478 | #8179. 2D Parentheses | maojun | WA | 176ms | 35472kb | C++20 | 2.4kb | 2024-06-02 15:56:46 | 2024-06-02 15:56:47 |
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);}
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 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)<mt(b.y,!b.o);});
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);
}
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: 0ms
memory: 16188kb
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: 14088kb
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: 9860kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Wrong Answer
time: 176ms
memory: 35472kb
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