QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#649256#5466. Permutation Compressionhei_yu_baiRE 1ms3772kbC++202.9kb2024-10-17 22:19:222024-10-17 22:19:22

Judging History

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

  • [2024-10-17 22:19:22]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3772kb
  • [2024-10-17 22:19:22]
  • 提交

answer

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

vector<int> bit;

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

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

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

const int N = 2e5 + 10;
vector<int> Log(N);

void init() {
	for (int i = 2; i < N; ++i) {
		Log[i] = Log[i >> 1] + 1;
	}
	return;
}

vector<vector<int>> st;
int tag;

void build(vector<int>& t) {
	int n = t.size(), logn = Log[n];
	st.resize(n, vector<int>(logn + 1));
	//tag = Log[n - 1];

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= logn; ++j) {
			st[j][i] = 0;
		}
	}

	for (int i = 0; i < n; ++i) st[i][0] = t[i];
	for (int i = 1; i <= logn; ++i) {
		int d = 1 << (i - 1);
		for (int j = 1; j + (1 << i) - 1 < n; ++j) {
			st[j][i] = max(st[j][i - 1], st[j + d][i - 1]);
		}
	}

	return;
}

int query(int l, int r) {
	int L = Log[r - l + 1];
	return max(st[l][L], st[r - (1 << L) + 1][L]);
}

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

	bit.resize(n + 1);
	vector<int> a(n + 1), b(m + 1), p(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[a[i]] = i;
		bit[i] = 0;
	}
	for (int i = 1; i <= m; ++i) cin >> b[i];

	multiset<int> s;
	s.insert(0);
	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;
	}

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

	build(t);

	vector<int> l(n + 1), r(n + 1);
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			int tl = 0, tr = p[i];
			while (tl + 1 < tr) {
				int mid = (tl + tr) >> 1;
				(query(mid, p[i]) > i ? tl : tr) = mid;
			}
			l[p[i]] = tl;

			tl = p[i], tr = n + 1;
			while (tl + 1 < tr) {
				int mid = (tl + tr) >> 1;
				(query(p[i], mid) > i ? tr : tl) = mid;
			}
			r[p[i]] = tr;

			//cout << p[i] << " " << l[p[i]] << " " << r[p[i]] << "\n";
		}
	}

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

	cout << "YES\n";
	return;
}

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

	init();

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

	return 0;
}

詳細信息

Test #1:

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

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: