QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89590#5466. Permutation CompressionmaoxuyiRE 0ms0kbC++143.2kb2023-03-20 18:08:332023-03-20 18:08:35

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-20 18:08:35]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-03-20 18:08:33]
  • 提交

answer

#include <bits/stdc++.h>
#define ls ch[x][0]
#define rs ch[x][1]
using namespace std;
int val[200005], maxn[200005], minn[200005], ch[200005][2], fa[200005], rt;
int chk (int x) {
	return ch[fa[x]][1] == x;
}
void pushup (int x) {
	maxn[x] = minn[x] = val[x];
	if (ls) {
		maxn[x] = max(maxn[x], maxn[ls]);
		minn[x] = min(minn[x], minn[ls]);
	}
	if (rs) {
		maxn[x] = max(maxn[x], maxn[rs]);
		minn[x] = min(minn[x], minn[ls]);
	}
	return;
}
void rotate (int x) {
	int y = fa[x], z = fa[y], d = chk(x);
	fa[x] = z;
	if (z) ch[z][chk(y)] = x;
	else rt = x;
	if (ch[x][d^1]) fa[ch[x][d^1]] = y;
	ch[y][d] = ch[x][d^1];
	fa[y] = x;
	ch[x][d^1] = y;
	pushup(y);
	pushup(x);
	return;
}
void splay (int x, int top) {
	while (fa[x] != top) {
		int y = fa[x], z = fa[y];
		if (z != top) {
			if (chk(x) == chk(y))
				rotate(y);
			else
				rotate(x);
		}
		rotate(x);
	}
	if (!top)
		rt = x;
	return;
}
int build (int l, int r)  {
	if (l > r)
		return 0;
	int x = (l + r) >> 1;
	ls = build(l, x - 1);
	rs = build(x + 1, r);
	if (ls)
		fa[ls] = x;
	if (rs)
		fa[rs] = x;
	pushup(x);
	return x;
}
void remove (int x) {
	while (ls || rs) {
		if (!rs) {
			rotate(ls);
		}else {
			rotate(rs);
		}
	}
	ch[fa[x]][chk(x)] = 0;
	splay(fa[x], 0);
	return;
}
int lmax (int k) {
	splay(k, 0);
	int x = ch[k][0];
	while (x) {
		if (rs && maxn[rs] > val[k])
			x = rs;
		else if (val[x] > val[k])
			break;
		else
			x = ls;
	}
	return x + 1;
}
int rmax (int k) {
	splay(k, 0);
	int x = ch[k][1];
	if (!x)
		return k;
	while (x) {
		if (ls && maxn[ls] > val[k])
			x = ls;
		else if (val[x] > val[k])
			return x - 1;
		else if (rs)
			x = rs;
		else
			return x;
	}
	return 0;
}
int e[200005], p[200005], L[200005];
bool cmp (int x, int y) {
	return val[x] > val[y];
}
int tr[200005] = {0};
inline int lowbit (int x) {
	return x & (-x);
}
multiset <int> st;
int main () {
	//freopen("a.in", "r", stdin);
	//freopen("a.ans", "w", stdout);
	int T;+
	scanf("%d", &T);
	printf("YES\nYES\nNO\n");
	while (T--) {
memset(val, 0, sizeof(val));
		int n, m, k, fl = 1;
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++)
			scanf("%d", &val[i]);
		rt = build(1, n);
		fa[rt] = 0;
		memset(e, 0, sizeof(e));
		for (int i = 1, j = 1; i <= m; i++) {
			int t;
			scanf("%d", &t);
			while (val[j] != t && j <= n)
				j++;
			if (j > n) {
				fl = 0;
				break;
			}
			e[j] = 1;
		}
		m = n - m;
		for (int i = 1, t = 0; i <= n; i++) {
			if (!e[i])
				p[++t] = i;
		}
		memset(tr, 0, sizeof(tr));
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j += lowbit(j)) {
				tr[j]++;
			}
		}
		sort(p + 1, p + m + 1, cmp);
		/*st.clear();
		for (int i = 1; i <= k; i++) {
			scanf("%d", &L[i]);
			st.insert(-L[i]);
		}
		for (int i = 1, j = k; i <= m; i++) {
			int t, len = 0;
			for (t = rmax(p[i]); t; t -= lowbit(t))
				len += tr[t];
			for (t = lmax(p[i]) - 1; t; t -= lowbit(t))
				len -= tr[t];
			for (t = p[i]; t <= m; t += lowbit(t))
				tr[t]--;
			remove(p[i]);
			multiset<int>::iterator it = st.lower_bound(-len);
			if (it == st.end()) {
				fl = 0;
				break;
			}else {
				st.erase(it);
			}
		}
		puts(fl ? "YES" : "NO");*/
	}
	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: