QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617987 | #5466. Permutation Compression | i0stream | WA | 1ms | 13888kb | C++14 | 3.5kb | 2024-10-06 18:00:18 | 2024-10-06 18:00:18 |
Judging History
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 (y<=mid) return query1(t<<1,l,mid,x,y,k,u);
if (x>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|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=0;i<=n+1;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;
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: 100
Accepted
time: 0ms
memory: 13888kb
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
output:
YES YES NO
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 11828kb
input:
100 2 1 2 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1 1 2 1 2 6 1 5 3 4 2 5 6 1 3 5 2 1 1 1 6 1 6 2 1 3 6 4 5 1 4 1 2 2 1 4 3 3 2 2 1 3 2 1 3 2 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 2 1 2 4 4 3 2 1 3 4 2 1 3 4 4 3 1 1 1 1 1 1 1 6 5 1 6 2 5 4 3 1 6 2 4 3 1 4 1 1 1 1 1 1 6 5 3 3 6 1 4 5 2 3 6 1 4 2 3 3 4 4 3 4 3 4 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES Y...
result:
wrong answer 45th lines differ - expected: 'NO', found: 'YES'