QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791592#5466. Permutation CompressionTom22lRE 2ms16024kbC++172.4kb2024-11-28 19:46:042024-11-28 19:46:04

Judging History

你现在查看的是最新测评结果

  • [2024-11-28 19:46:04]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:16024kb
  • [2024-11-28 19:46:04]
  • 提交

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 ...

output:


result: