QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75746 | #5466. Permutation Compression | chenshi# | WA | 2ms | 5000kb | C++ | 1.7kb | 2023-02-06 09:45:19 | 2023-02-06 09:45:20 |
Judging History
answer
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int o=2e5+10;
int T,n,m,K,a[o],b[o],p,st[o],tp,mx[o*4];set<int> S;set<int>::iterator iter;
void build(int id,int l,int r){
if(l==r){mx[id]=a[l];return;}
int md=l+r>>1;
build(id<<1,l,md);build((id<<1)|1,md+1,r);
mx[id]=max(mx[id<<1],mx[(id<<1)|1]);
}
void modify(int id,int pos,int val,int l=1,int r=n){
if(l==r){mx[id]=val;return;}
int md=l+r>>1;
if(pos<=md) modify(id<<1,pos,val,l,md);
else modify((id<<1)|1,pos,val,md+1,r);
mx[id]=min(mx[id<<1],mx[(id<<1)|1]);
}
int bs1(int id,int pos,int val,int l=1,int r=n){
if(mx[id]<=val) return l-1;
if(l==r) return l;
int md=l+r>>1;
if(pos<=md) return bs1(id<<1,pos,val,l,md);
int res=bs1((id<<1)|1,pos,val,md+1,r);
if(res==md) return bs1(id<<1,pos,val,l,md);
return res;
}
int bs2(int id,int pos,int val,int l=1,int r=n){
if(mx[id]<=val) return r+1;
if(l==r) return r;
int md=l+r>>1;
if(pos>md) return bs2((id<<1)|1,pos,val,md+1,r);
int res=bs2(id<<1,pos,val,l,md);
if(res==md+1) return bs2((id<<1)|1,pos,val,md+1,r);
return res;
}
inline bool cmp(int A,int B){return a[A]<a[B];}
inline void slv(){
scanf("%d%d%d",&n,&m,&K);p=1;tp=0;
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=m;++i) scanf("%d",&b[i]);
for(int l;K--;S.insert(l)) scanf("%d",&l);
for(int i=1;i<=n;++i)
if(p<=m&&a[i]==b[p]) ++p;
else st[++tp]=i;
if(p<=m){printf("NO\n");return;}
sort(st+1,st+tp+1,cmp);
build(1,1,n);
for(int i=tp,len;i;--i){
len=bs2(1,st[i],a[st[i]])-bs1(1,st[i],a[st[i]])-1;
if((iter=S.upper_bound(len))==S.begin()){printf("NO\n");return;}
S.erase(--iter);modify(1,a[st[i]],0);
}
printf("YES\n");
}
int main(){
for(scanf("%d",&T);T--;S.clear()) slv();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5000kb
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: 2ms
memory: 3068kb
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 NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES NO YES YES YES YES YES NO NO YES YES YES NO YES NO NO YES NO NO YES YES YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES Y...
result:
wrong answer 4th lines differ - expected: 'YES', found: 'NO'