QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617918 | #5466. Permutation Compression | i0stream | TL | 0ms | 0kb | C++14 | 3.5kb | 2024-10-06 17:43:14 | 2024-10-06 17:43:14 |
answer
#include <bits/stdc++.h>
using namespace std;
const int N=2*1e5+100;
int tr1[N<<2],tr2[N],tr3[N<<2],L[N<<2],R[N<<2];
int a[N],buc[N],wt,n,m,t,T,succ;
struct node{
int id,s;
}S[N];
inline bool cmp(node x,node y){return x.s>y.s;}
int read(){
int x=0,c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') x=x*10+c-48,c=getchar();
return x;
}
void build1(int t,int l,int r){
L[t]=l;R[t]=r;
if (l==r){
tr1[t]=a[l];
return;
}
int mid=l+r>>1;
build1(t<<1,l,mid);
build1(t<<1|1,mid+1,r);
tr1[t]=max(tr1[t<<1],tr1[t<<1|1]);
}
void modify1(int t,int l,int r,int x,int k){
if (l==r){
tr1[t]=k;
return;
}
int mid=l+r>>1;
if (x<=mid) modify1(t<<1,l,mid,x,k);
else modify1(t<<1|1,mid+1,r,x,k);
tr1[t]=max(tr1[t<<1],tr1[t<<1|1]);
}
int query1(int t,int l,int r,int x,int y,int k,int u){
if (x==l && r==y){
if (tr1[t]>u) return t;
else return 0;
}
int mid=l+r>>1;
if (x<=mid) return query1(t<<1,l,mid,x,y,k,u);
if (y>mid) return query1(t<<1|1,mid+1,r,x,y,k,u);
int t1=query1(t<<1,l,mid,x,mid,k,u),t2=query1(t<<1,mid+1,r,mid+1,y,k,u);
if (t1==0 || t2==0) return t1+t2;
if (k==0) return t2;
else return t1;
}
int dfs1(int t,int l,int r,int k,int u){
if (l==r) return l;
int mid=l+r>>1;
if (k==0){
if (tr1[t<<1|1]>u) return dfs1(t<<1|1,mid+1,r,k,u);
else return dfs1(t<<1,l,mid,k,u);
}else{
if (tr1[t<<1]>u) return dfs1(t<<1,l,mid,k,u);
else return dfs1(t<<1|1,mid+1,r,k,u);
}
}
inline int lowbit(int x){return x&(-x);}
void modify2(int x,int k){
while (x<=n){
tr2[x]+=k;
x+=lowbit(x);
}
}
int query2(int x){
int ans=0;
while (x){
ans+=tr2[x];
x-=lowbit(x);
}
return ans;
}
void build3(int t,int l,int r){
tr3[t]=0;
if (l==r) return;
int mid=l+r>>1;
build3(t<<1,l,mid);
build3(t<<1|1,mid+1,r);
}
void modify3(int t,int l,int r,int x,int k){
if (l==r){
tr3[t]+=k;
return;
}
int mid=l+r>>1;
if (x<=mid) modify3(t<<1,l,mid,x,k);
else modify3(t<<1|1,mid+1,r,x,k);
tr3[t]=tr3[t<<1]+tr3[t<<1|1];
}
int query3(int t,int l,int r,int x,int y){
if (l==x && r==y){
if (tr3[t]==0) return 0;
else return t;
}
int mid=l+r>>1;
if (y<=mid) return query3(t<<1,l,mid,x,y);
if (x>mid) return query3(t<<1|1,mid+1,r,x,y);
int t1=query3(t<<1,l,mid,x,mid),t2=query3(t<<1|1,mid+1,r,mid+1,y);
if (t1==0 || t2==0) return t1+t2;
return t2;
}
int dfs3(int t,int l,int r){
if (l==r) return l;
int mid=l+r>>1;
if (tr3[t<<1|1]>0) return dfs3(t<<1|1,mid+1,r);
return dfs3(t<<1,l,mid);
}
int main(){
T=read();
while (T--){
n=read();m=read();t=read();
for (int i=1;i<=n;i++) buc[i]=0;wt=0;
for (int i=1;i<=n;i++) a[i]=read();
a[0]=n+1;a[n+1]=n+2;
for (int i=1;i<=m;i++) buc[read()]++;
for (int i=1;i<=n;i++)
if (!buc[a[i]]) S[++wt]=(node){i,a[i]};
sort(S+1,S+wt+1,cmp);
build1(1,0,n+1);
for (int i=1;i<=n;i++) tr2[i]=0;
build3(1,0,n+1);
modify3(1,0,n+1,0,1);
for (int i=1;i<=t;i++) modify3(1,0,n+1,read(),1);
succ=1;
for (int i0=1;i0<=wt;i0++){
int s=S[i0].s,id=S[i0].id;
//cout<<s<<' '<<id<<endl;
int tj=query1(1,0,n+1,0,id-1,0,s),tk=query1(1,0,n+1,id+1,n+1,1,s);
int j=dfs1(tj,L[tj],R[tj],0,s),k=dfs1(tk,L[tk],R[tk],1,s);
int l0=k-j-1-query2(k-1)+query2(j);
modify1(1,0,n+1,id,0);
modify2(id,1);
int tz=query3(1,0,n+1,0,l0);
int z=dfs3(tz,L[tz],R[tz]);
if (z==0){
succ=0;
break;
}
modify3(1,0,n+1,z,-1);
}
puts(succ?"YES":"NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
3 5 2 3 5 1 3 2 4 5 2 1 2 4 5 5 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 3 2 2 3 1 2 3 2 2 3