QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75749 | #5466. Permutation Compression | chenshi# | WA | 2ms | 5008kb | C++ | 1.7kb | 2023-02-06 09:47:18 | 2023-02-06 09:47:19 |
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,st[i],0);
}
printf("YES\n");
}
int main(){
for(scanf("%d",&T);T--;S.clear()) slv();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 5008kb
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: 4920kb
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'