QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#75751 | #5466. Permutation Compression | chenshi# | WA | 2ms | 5080kb | C++ | 1.8kb | 2023-02-06 09:49:23 | 2023-02-06 09:49:25 |
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];multiset<int> S;multiset<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(S.find(*--iter));modify(1,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: 5080kb
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: 5008kb
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 YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES...
result:
wrong answer 28th lines differ - expected: 'NO', found: 'YES'