QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648254#5466. Permutation CompressionRepeater#RE 0ms0kbC++202.2kb2024-10-17 17:56:412024-10-17 17:56:42

Judging History

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

  • [2024-10-17 17:56:42]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-17 17:56:41]
  • 提交

answer

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<set>

using i64 = long long;

vector<int> arr;

void update(int p){
	for(int i = p; i < arr.size(); i += i & -i){
		arr[i]++;
	}
	return;
}

int getsum(int p){
	int sum = 0;
	for(int i = p; i > 0; i -= i & -i){
		sum += arr[i];
	}
	return sum;
}

int getsum(int l, int r){
	return getsum(r) - getsum(l - 1);
}

void solve(){
	int n, m, k;
	cin >> n >> m >> k;

	arr.resize(n + 2);

	vector<int> a(n + 2), b(m + 1), p(n + 1);
	a[0] = a[n + 1] = 1e9;

	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
		arr[i] = 0;
	}
	for(int i = 1; i <= m; ++i) cin >> b[i];

	multiset<int> s;
	for(int i = 1; i <= k; ++i) {
		int v = 0;
		cin >> v;
		s.insert(v);
	}

	if(k < n - m) {
		cout << "NO\n";
		return;
	}

	int tp = 1;
	for(int i = 1; i <= m; ++i){
		while(tp <= n && a[tp] != b[i]) ++tp;
	}

	if(tp == n + 1){
		cout << "NO\n";
		return;
	}

	s.insert(0), s.insert(1e9);

	vector<bool> vis(n + 2);
	for(int i = 1; i <= m; ++i){
		vis[b[i]] = true;
	}

	vector<int> l(n + 2), r(n + 2, n + 1), stk(n + 2);
	int t = -1;

	for(int i = 0; i <= n + 1; ++i){
		while(t != -1 && a[i] > a[stk[t]]) --t;
		if(t != -1) l[i] = stk[t];
		if(vis[a[i]]) stk[++t] = i; 
	}

	t = -1;
	for(int i = n + 1; i >= 0; --i){
		while(t != -1 && a[i] > a[stk[t]]) --t;
		if(t != -1) r[i] = stk[t];
		if(vis[a[i]]) stk[++t] = i;
	}

	for(int i = 1; i <= n; ++i){
		if(vis[i]) l[p[i]] = r[p[i]] = p[i];
	}

	l[0] = r[0] = 0;
	l[n + 1] = r[n + 1] = n + 1;

	// for(int i = 0; i <= n + 1; ++i){
	// 	cout << i << " " << l[i] << " " << r[i] << "\n";
	// }


	for(int i = n; i >= 1; --i){
		if(!vis[i]){
			int j = p[i];
			int q = getsum(l[j] + 1, r[j] - 1);
			auto t = prev(s.upper_bound(r[j] - l[j] - 1 - q));
			//cout << i << " " << l[i] << " " << r[i] << " " << q << " " << (*t) << "\n";
			if(*t == 0){
				cout << "NO\n";
				return;
			}
			else{
				s.extract(*t);
				update(j);
			}
		}
	}

	cout << "YES\n";

	return;
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	cin >> t;
	while(t--) solve();

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

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:


result: