QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425453 | #8179. 2D Parentheses | jinqihao2023 | RE | 6ms | 57172kb | C++14 | 4.4kb | 2024-05-30 11:19:07 | 2024-05-30 11:19:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,inf=2e9;
typedef unsigned long long ull;
int n,ax[N],ay[N],bx[N],by[N],cx[N],cy[N],a[N],pos[N];
mt19937_64 rd(19491001);
struct Seg_tree
{
struct STree{int l,r,minn;}t[N*4];
void pushup(int p){t[p].minn=min(t[p*2].minn,t[p*2+1].minn);}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].minn=inf;if(l==r)return t[p].minn=a[l],void();
int mid=l+r>>1;build(p*2,l,mid),build(p*2+1,mid+1,r),pushup(p);
}
void change(int p,int x,int v)
{
if(t[p].l==t[p].r)return t[p].minn=v,void();int mid=t[p].l+t[p].r>>1;
if(x<=mid)change(p*2,x,v);else change(p*2+1,x,v);pushup(p);
}
int ask(int p,int l,int r)
{
if(l<=t[p].l && t[p].r<=r)return t[p].minn;
int mid=t[p].l+t[p].r>>1,res=inf;
if(l<=mid)res=min(res,ask(p*2,l,r));if(mid<r)res=min(res,ask(p*2+1,l,r));
return res;
}
}t1;
struct Seg_tree1
{
struct STree{int l,r;ull tag,val;bool col;}t[N*4];
void update(int p,ull v){t[p].tag^=v,t[p].val^=v;}
void pushdown(int p){if(t[p].tag)update(p*2,t[p].tag),update(p*2+1,t[p].tag),t[p].tag=0;}
void pushup(int p)
{
t[p].val=t[p*2].val;
if(t[p*2].col && t[p*2+1].col && t[p*2].val==t[p*2+1].val)t[p].col=1;else t[p].col=0;
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].col=1;if(l==r)return ;int mid=l+r>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r);
}
void change(int p,int l,int r,ull v)
{
if(l<=t[p].l && t[p].r<=r)return update(p,v);pushdown(p);
int mid=t[p].l+t[p].r>>1;if(l<=mid)change(p*2,l,r,v);if(mid<r)change(p*2+1,l,r,v);
pushup(p);
}
pair<ull,bool>ask(int p,int l,int r)
{
if(l<=t[p].l && t[p].r<=r)return {t[p].val,t[p].col};pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(l>mid)return ask(p*2+1,l,r);if(mid>=r)return ask(p*2,l,r);
pair<ull,bool>resl=ask(p*2,l,r),resr=ask(p*2+1,l,r);
return {resl.first,(resl.second&resr.second&(resl.first==resr.first))};
}
}t2;
bool cmp(int a,int b){if(by[a]!=by[b])return by[a]<by[b];return bx[a]<bx[b];}
int mat[N];
set<pair<int,int> >ss[N];
struct abc{int l,r;ull v;};
vector<abc>in[N],out[N];
ull vv[N];
bool cmp1(abc a,abc b){if(a.l!=b.l)return a.l<b.l;return a.r>b.r;}
bool cmp2(abc a,abc b){if(a.l!=b.l)return a.l>b.l;return a.r<b.r;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)vv[i]=rd();
for(int i=1;i<=n;i++)scanf("%d %d",&ax[i],&ay[i]),cx[0]++,cx[cx[0]]=ax[i],cy[0]++,cy[cy[0]]=ay[i];
for(int i=1;i<=n;i++)scanf("%d %d",&bx[i],&by[i]),cx[0]++,cx[cx[0]]=bx[i],cy[0]++,cy[cy[0]]=by[i];
sort(cx+1,cx+cx[0]+1),cx[0]=unique(cx+1,cx+cx[0]+1)-cx-1;
sort(cy+1,cy+cy[0]+1),cy[0]=unique(cy+1,cy+cy[0]+1)-cy-1;
for(int i=1;i<=n;i++)ax[i]=lower_bound(cx+1,cx+cx[0]+1,ax[i])-cx,ay[i]=lower_bound(cy+1,cy+cy[0]+1,ay[i])-cy,bx[i]=lower_bound(cx+1,cx+cx[0]+1,bx[i])-cx,by[i]=lower_bound(cy+1,cy+cy[0]+1,by[i])-cy;
for(int i=1;i<=n;i++)pos[i]=i;sort(pos+1,pos+n+1,cmp);
for(int i=1;i<=n;i++)ss[ax[i]].insert({ay[i],i});
for(int i=1;i<=cx[0];i++)if(ss[i].size())a[i]=(*ss[i].begin()).first;else a[i]=inf;
// for(int i=1;i<=cx[0];i++)printf("%d ",a[i]);printf("\n");
t1.build(1,1,cx[0]),t2.build(1,1,cy[0]-1);
for(int i=1;i<=n;i++)
{
int x=pos[i];
int l=1,r=bx[x]-1,pos=-1;
while(l<=r)
{
int mid=l+r>>1;
if(t1.ask(1,mid,bx[x]-1)<by[x])pos=mid,l=mid+1;
else r=mid-1;
}
if(pos==-1){printf("No\n");return 0;}
auto it=--ss[pos].lower_bound({bx[x],0});ss[pos].erase(it);
if(ss[pos].size())t1.change(1,pos,(*ss[pos].begin()).first);else t1.change(1,pos,inf);
int y=(*it).second;
mat[y]=x;
}
// for(int i=1;i<=n;i++)printf("%d ",mat[i]);printf("\n");
for(int i=1;i<=n;i++)in[ax[i]].push_back((abc){ay[i],by[mat[i]]-1,vv[i]}),out[bx[mat[i]]].push_back((abc){ay[i],by[mat[i]]-1,vv[i]});
for(int i=1;i<=cx[0];i++)
{
// cout<<t2.t[5].val<<" "<<t2.t[5].col<<endl;
sort(out[i].begin(),out[i].end(),cmp2);
sort(in[i].begin(),in[i].end(),cmp1);
for(auto j:out[i])
{
// cout<<j.l<<" "<<j.r<<" "<<j.v<<" "<<t2.ask(1,j.l,j.r).first<<" "<<t2.ask(1,j.l,j.r).second<<endl;
if(!t2.ask(1,j.l,j.r).second){printf("No\n");return 0;}
t2.change(1,j.l,j.r,j.v);
}
for(auto j:in[i])
{
// cout<<j.l<<" "<<j.r<<" "<<j.v<<" "<<t2.ask(1,j.l,j.r).first<<" "<<t2.ask(1,j.l,j.r).second<<endl;
if(!t2.ask(1,j.l,j.r).second){printf("No\n");return 0;}
t2.change(1,j.l,j.r,j.v);
}
}
printf("Yes\n");
for(int i=1;i<=n;i++)printf("%d\n",mat[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 55132kb
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: 4ms
memory: 55024kb
input:
2 1 0 0 1 2 3 3 2
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 6ms
memory: 57172kb
input:
1 1 1 0 0
output:
No
result:
ok answer is NO
Test #4:
score: -100
Runtime Error
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...