QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#592343#5466. Permutation Compressionice_cupWA 2ms9844kbC++142.3kb2024-09-26 22:00:052024-09-26 22:00:09

Judging History

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

  • [2024-09-26 22:00:09]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9844kb
  • [2024-09-26 22:00:05]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define MID int mid=(l+r)>>1;
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
#define siz(a) int(a.size())
int n,m,k,a[200100],pre[200100],vis[200100],len[200100],top;
int TTT;
int ck[200100];
int l[200100],r[200100];
int s[200100];
int tr[200100];
int low(int x){return x&(-x);}
void add1(int x,int v){
	for(int i=x;i<=n;i+=low(i)){
		tr[i]=max(tr[i],v);
	}
}
void add2(int x,int v){
	for(int i=x;i<=n;i+=low(i)){
		tr[i]=min(tr[i],v);
	}
}
void add3(int x,int v){
	for(int i=x;i<=n;i+=low(i)){
		tr[i]+=v;
	}
}
int pr1(int x){
	int ans=0;
	for(int i=x;i;i-=low(i)){
		ans=max(ans,tr[i]);
	}
	return ans;
}
int pr2(int x){
	int ans=n+1;
	for(int i=x;i;i-=low(i)){
		ans=min(ans,tr[i]);
	}
	return ans;
}
int pr3(int x){
	x=min(x,n);
	int ans=0;
	for(int i=x;i;i-=low(i)){
		ans+=tr[i];
	}
	return ans;
}
void solveclr(){
	for(int i=1;i<=n;i++){
		vis[i]=len[i]=tr[i]=0;
	}
	top=0;
}
void solve(){
	// cout<<pr3(0);
	solveclr();s[0]=0x3f3f3f3f;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[a[i]]=i;
	}
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		ck[i]=pre[x];
		vis[x]=1;
	}
	for(int i=1;i<m;i++){
		if(ck[i]>ck[i+1]){
			cout<<"NO\n";
			return;
		}
	}
	for(int i=1;i<=k;i++){
		cin>>s[i];
	}
	sort(s+1,s+1+k);
	for(int i=1;i<=n;i++){
		if(vis[a[i]])add1(n+1-a[i],i);
		else{
			l[a[i]]=pr1(n+1-a[i]);
		}
	}
	for(int i=1;i<=n;i++)tr[i]=n+1;
	for(int i=n;i>=1;i--){
		if(vis[a[i]])add2(n+1-a[i],i);
		else{
			r[a[i]]=pr2(n+1-a[i]);
		}
	}
	for(int i=1;i<=n;i++)tr[i]=0;
	for(int i=1;i<=n;i++){
		add3(pre[i],1);
		if(vis[i])continue;
		len[++top]=pr3(r[i])-pr3(l[i]);
		// cout<<i<<' '<<l[i]<<' '<<r[i]<<' '<<len[top]<<'\n';
	}
	sort(len+1,len+1+top);
	int j=k,fl=0;
	for(int i=top;i>=1;i--){
		while(s[j]>len[i]&&j!=0)j--;
		if(s[j]>len[i]){
			fl=1;break;
		}
		else j--;
	}
	if(TTT<=3)cout<<(fl?"NO":"YES")<<endl;
	else {
		for(int i=1;i<=n;i++)cout<<a[i]<<' ';
			cout<<'/';
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>TTT;
	for(int i=1;i<=TTT;i++){
		solve();
	}
}
/*
1
3 1 2
1 2 3
2
1 4
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7784kb

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: 9844kb

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:

2 1 /1 2 /1 2 /3 4 2 5 6 1 /2 1 3 6 4 5 /2 1 3 /1 /1 /2 1 /2 1 3 4 /1 /6 2 5 4 3 1 /1 /3 6 1 4 5 2 /3 4 1 2 /3 4 5 1 2 /2 4 3 1 /1 /4 2 3 5 1 6 /3 2 1 /2 1 /2 3 1 /2 3 5 1 4 /1 /1 5 6 3 4 2 /3 1 4 2 /1 2 3 /2 3 5 6 1 4 /1 /1 4 2 5 3 /3 1 4 2 /1 /2 1 6 5 4 3 /2 4 3 6 5 1 /4 2 3 5 1 6 /1 /3 1 2 /1 /4 ...

result:

wrong answer 1st lines differ - expected: 'YES', found: '2 1 /1 2 /1 2 /3 4 2 5 6 1 /2 ... /4 5 2 1 3 /1 /2 3 6 4 5 1 /NO'