QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88990#5466. Permutation CompressionSmall_BlackCompile Error//C++142.7kb2023-03-18 09:23:352023-03-18 09:23:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-18 09:23:37]
  • 评测
  • [2023-03-18 09:23:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mpr make_pair
//mt19937_64 ra(time(0) ^ (*new char));
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
const int SIZE = 200005;
const int mod = 998244353;
int n, m, K, T;
int a[SIZE], b[SIZE];
int l[SIZE];
bool v[SIZE], used[SIZE];
int st[SIZE], top;
int nx[SIZE], pr[SIZE];
int c[SIZE];

inline int rd(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x*f;
}

bool cmp(int x, int y){
	return a[x] > a[y];	
}

int lowbit(int x){
	return x & (-x);	
}

void add(int x, int val){
	for(int i = x; i <= n; i+=lowbit(i)) c[i] += val;	
}

int ask(int x){
	int jl = 0;
	for(int i = x; i; i-=lowbit(i)) jl += c[i];
	return jl;
}

int main(){
	T = rd();
	while(T--){
		n = rd(), m = rd(), K = rd();
		for(int i = 1; i <= n; i++) c[i] = 0;
		for(int i = 1; i <= n; i++) a[i] = rd(), v[i] = 1, add(i, 1);
		for(int i = 1; i <= m; i++) b[i] = rd(), v[b[i]] = 0;
		for(int i = 1; i <= K; i++) l[i] = rd(), used[i] = 0;
		used[0] = used[n+1] = 0;
		sort(l+1, l+K+1); top = 0;
		for(int i = 1; i <= n; i++){
			while(top && a[st[top]] < a[i]) nx[st[top]] = i, top--;
			st[++top] = i;
		}
		while(top) nx[st[top]] = n+1, top--;
		for(int i = n; i >= 1; i--){
			while(top && a[st[top]] < a[i]) pr[st[top]] = i, top--;
			st[++top] = i;
		}
		while(top) pr[st[top]] = 0, top--;
		for(int i = 1; i <= n; i++){
			if(v[a[i]]) st[++top] = i;
			v[a[i]] = 0;
		}
		v[0] = v[k+1] = 0;
		sort(st+1, st+top+1, cmp);
//		for(int i = 1; i <= top; i++) printf("%d ", st[i]);
//		puts("");
		bool ans = 1; 
		for(int i = 1; i <= top; i++){
			int prr = pr[st[i]], nxx = nx[st[i]];
			while(v[prr]) prr = pr[prr];
			while(v[nxx]) nxx = nx[nxx];
			prr++, nxx--;
//			cout << prr << " " << nxx << endl;
			int x = ask(nxx) - (prr==1?0:ask(prr-1)), jl = 0;
//			cout << x << endl;
			for(int j = K; j >= 1; j--){
				if(l[j] > x || used[j]) continue;
				jl = j; break;
			}
			if(jl == 0){
				ans = 0;
				break;
			}
			used[jl] = 1; v[st[i]] = 1; add(st[i], -1);
		}
		if(ans == 0){
			printf("NO\n");
			continue;
		}
		int now = 1;
		for(int i = 1; i <= n; i++){
			if(!v[i]){
				if(a[i] == b[now]) now++;
				else{
					ans = 0;
					break;
				}
			}
		}
		if(ans) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
/*
2
8 3 8
8 3 1 7 2 5 4 6
8 7 2
4 4 2 2 1 6 6 6
8 4 7
5 2 6 8 3 4 1 7
6 8 1 7
3 2 2 1 5 5 5


*/

Details

answer.code: In function ‘int main()’:
answer.code:77:26: error: ‘k’ was not declared in this scope
   77 |                 v[0] = v[k+1] = 0;
      |                          ^