QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#655006#5466. Permutation Compressiontz3528RE 0ms0kbC++231.6kb2024-10-18 23:43:022024-10-18 23:43:03

Judging History

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

  • [2024-10-18 23:43:03]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-18 23:43:02]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

int tr[N];

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

void add(int pos, int d) {
	for(int i = pos; i < N; i += lowbit(i)) {
		tr[i] += d;
	}
}

int query(int pos) {
	int res = 0;
	for(int i = pos; i; i -= lowbit(i)) {
		res += tr[i];
	}
	return res;
}

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	std::vector<int> pos(n + 10), has(n + 10);
	for(int i = 1, x; i <= n; i ++ ) {
		cin >> x;
		pos[x] = i;
	}
	vector<int> a(m + 1);
	for(int i = 1, x; i <= m; i ++ ) {
		cin >> x;
		has[x] = 1;
		a[i] = x;
	}
	int flag=0;
	for(int i = 1; i < m; i ++ ) {
		if(pos[a[i + 1]] < pos[a[i]]) {
			flag=1;
		}
	}
	multiset<int> st;
	st.insert(0);
	st.insert(n + 1);
	for(int i = 1, x; i <= k; i ++ ) {
		cin >> x;
		st.insert(x);
	}
	if(flag){
		cout<<"NO\n";
		return ;
	}
	set<int> p;
	p.insert(0);
	p.insert(n + 1);
	bool fg = 0;
	vector<int> need_del(n + 1);
	for(int i = n; i >= 1; i -- ) {
		if(!has[i]) {
			auto it = p.upper_bound(pos[i]);
			int l = *prev(it), r = *it;
			int w = r - l - 1-(query(r)-query(l));
			auto it2 = prev(st.upper_bound(w));
			if(*it2 == 0) {
				fg = 1;
				break;
			} else {
				add(pos[i],1);
				st.erase(it2);
			}
		} else {
			p.insert(pos[i]);
		}
	}
	if(fg) {
		cout << "NO\n";
	} else {
		cout << "YES\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	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: