QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791314 | #5466. Permutation Compression | Tom22l | RE | 0ms | 13928kb | C++17 | 2.2kb | 2024-11-28 18:02:19 | 2024-11-28 18:02:19 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
int x=0;
char ch=getchar();bool f=0;
while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int a[200005];
int pos[200005];
int b[200005];
bool c[200005];
int pre[200005];
int aft[200005];
set<int> l;
int stk[200005];
set<int> sk;
int n;
int s[200005];
int lowbit(int x){
return x&(-x);
}
void update(int x){
for(;x<=n;x+=lowbit(x))
s[x]+=1;
}
int query(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=s[x];
return ans;
}
int res;
signed main(){
set<int>::iterator it;
int T=Read();
while(T--){
n=Read();int m=Read(),k=Read();
for(int i=1;i<=n;i++)a[i]=Read(),pos[a[i]]=i;
for(int i=1;i<=m;i++)b[i]=Read();
int p1=1;
for(int i=1;i<=n;i++){
if(a[i]==b[p1]) c[i]=1,p1++;
else c[i]=0;
}
for(int i=1;i<=k;i++){
int d=Read();l.insert(d);
}
if(p1!=m+1){
printf("NO\n");
l.clear();
continue;
}
res=1;
stk[1]=0;
sk.insert(0);
for(int i=1;i<=n;i++){
if(c[i]){
while(stk[res]<a[i]&&res){
sk.erase(stk[res]);
res--;
}
stk[++res]=a[i];
sk.insert(stk[res]);
}else{
it=lower_bound(sk.begin(),sk.end(),a[i]);
if(it==sk.end()) pre[i]=0;
else pre[i]=pos[*it];
}
}
sk.clear();
res=1;
stk[1]=0;
for(int i=n;i>=1;i--){
if(c[i]){
while(stk[res]<a[i]&&res){
sk.erase(stk[res]);
res--;
}
stk[++res]=a[i];
sk.insert(stk[res]);
}else{
it=lower_bound(sk.begin(),sk.end(),a[i]);
if(it==sk.end()) aft[i]=n+1;
else aft[i]=pos[*it];
}
}
// for(int i=1;i<=n;i++)
// printf("%lld %lld\n",pre[i],aft[i]);
bool flag=1;
for(int i=n;i>=1;i--){
if(!c[pos[i]]){
int len=aft[pos[i]]-pre[pos[i]]-1;
int mis=query(aft[pos[i]])-query(pre[pos[i]]);
len-=mis;
// cout<<pos[i]<<' '<<i<<' '<<len<<endl;
it=lower_bound(l.begin(),l.end(),len+1);it--;
if(it==l.end()){
flag=0;
printf("NO\n");
break;
}
l.erase(it);
update(pos[i]);
}
}if(flag)printf("YES\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 13928kb
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
Runtime Error
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 ...