QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791592 | #5466. Permutation Compression | Tom22l | RE | 2ms | 16024kb | C++17 | 2.4kb | 2024-11-28 19:46:04 | 2024-11-28 19:46:04 |
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[402205];
int pos[402205];
int b[402205];
bool c[402205];
int pre[402205];
int aft[402205];
int stk[402205];
int n;
int s[402205];
int lowbit(int x){
return x&(-x);
}
void update(int x){
for(;x<=n+100;x+=lowbit(x))
s[x]+=1;
}
int query(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=s[x];
return ans;
}
int s2[402205];
void update2(int x,int y){
for(;x<=n+100;x+=lowbit(x))
s2[x]+=y;
}
int query2(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=s2[x];
return ans;
}
int res;
signed main(){
int T=Read();
for(int t=1;t<=T;t++){
set<int>::iterator it;
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;
b[m+1]=0;
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();update2(d,1);
}
if(p1!=m+1){
printf("NO\n");
continue;
}
res=1;
stk[1]=0;
for(int i=1;i<=n;i++){
if(c[i]){
while(stk[res]<a[i]&&res)res--;
stk[++res]=a[i];
}else{
int l=1,r=res;
pre[i]=0;
while(l<=r){
int mid=(l+r)>>1;
if(stk[mid]>a[i])pre[i]=pos[stk[mid]],l=mid+1;
else r=mid-1;
}
}
}
res=1;
stk[1]=0;
for(int i=n;i>=1;i--){
if(c[i]){
while(stk[res]<a[i]&&res)res--;
stk[++res]=a[i];
}else{
int l=1,r=res;
aft[i]=n+1;
while(l<=r){
int mid=(l+r)>>1;
if(stk[mid]>a[i]) aft[i]=pos[stk[mid]],l=mid+1;
else r=mid-1;
}
}
}
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;
int pt=query2(len);
if(pt<=0){
printf("NO\n");
flag=0;
break;
}
int lft=1,rgt=len;
int aim=0;
while(lft<=rgt){
int mid=(lft+rgt)>>1;
if(query2(mid)==pt) aim=mid,rgt=mid-1;
else lft=mid+1;
}
update2(aim,-1);
update(pos[i]);
}
}
if(flag)printf("YES\n");
for(int i=1;i<=n;i++) s[i]=0,s2[i]=0;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 16024kb
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 ...