Submission #37279

#	Time	Username	Problem	Language	Result	Execution time	Memory
37279		aome	Cake (CEOI14_cake)	C++14	100 / 100	579 ms	8880 KiB

cake

#include <bits/stdc++.h>
using namespace std;

const int N = 250005;

int n, start, q;
int a[N], it[4 * N];
bool in[N];
vector<int> top10;

void build(int i, int l, int r) {
	if (l == r) {
		if (!in[l]) it[i] = a[l]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void prepare() {
	vector<int> pos;
	for (int i = 1; i <= n; ++i) pos.push_back(i);
	sort(pos.begin(), pos.end(), [&] (int x, int y) {
		return a[x] > a[y];
	});
	for (int i = 0; i < min(n, 10); ++i) top10.push_back(pos[i]), in[pos[i]] = 1; 
	build(1, 1, n);
}

void upd(int i, int l, int r, int pos, int val) {
	if (l == r) {
		it[i] = val; return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) upd(i << 1, l, mid, pos, val);
	else upd(i << 1 | 1, mid + 1, r, pos, val);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}

int get(int i, int l, int r, int L, int R) {
	if (l > R || L > r) return 0;
	if (L <= l && r <= R) return it[i];
	int mid = (l + r) >> 1;
	return max(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid + 1, r, L, R));
}

int findL(int i, int l, int r, int val) {
	if (l >= start || it[i] <= val) return 0;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = findL(i << 1 | 1, mid + 1, r, val);
	if (res != 0) return res;
	return findL(i << 1, l, mid, val);
}

int findR(int i, int l, int r, int val) {
	if (r <= start || it[i] <= val) return n + 1;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = findR(i << 1, l, mid, val);
	if (res != n + 1) return res;
	return findR(i << 1 | 1, mid + 1, r, val);
}

void solveL(int pos) {
	int res = start - pos;
	int mx = get(1, 1, n, pos, start - 1);
	for (auto i : top10) {
		if (i < start && i >= pos) mx = max(mx, a[i]);
	} 
	int cur = findR(1, 1, n, mx);
	for (auto i : top10) {
		if (i > start && a[i] > mx) cur = min(cur, i);
	}
	res += (cur - 1) - start;
	printf("%d\n", res);
}

void solveR(int pos) {
	int res = pos - start;
	int mx = get(1, 1, n, start + 1, pos);
	for (auto i : top10) {
		if (i > start && i <= pos) mx = max(mx, a[i]);
	} 
	int cur = findL(1, 1, n, mx);
	for (auto i : top10) {
		if (i < start && a[i] > mx) cur = max(cur, i);
	}
	res += start - (cur + 1);
	printf("%d\n", res);
}

void modify(int pos, int e) {
	int sz = top10.size();
	vector<int> buffer = top10; top10.clear();
	for (int i = 0; i < e; ++i) {
		a[buffer[i]]++, top10.push_back(buffer[i]);
	}
	a[pos] = a[buffer[e]] + 1, top10.push_back(pos);
	if (!in[pos]) {
		for (int i = e; i < sz - 1; ++i) {
			top10.push_back(buffer[i]);
		} 
		in[pos] = 1, in[buffer.back()] = 0;
		upd(1, 1, n, pos, 0), upd(1, 1, n, buffer.back(), a[buffer.back()]);
	}
	else {
		for (int i = e; i < sz; ++i) {
			if (buffer[i] != pos) top10.push_back(buffer[i]);
		}
	}
	// for (int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << '\n';
	// for (int i = 0; i < min(n, 10); ++i) cout << top10[i] << ' '; cout << '\n';
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin >> n >> start;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	prepare();
	cin >> q;
	while (q--) {
		char type; cin >> type;
		if (type == 'F') { 	
			int pos; cin >> pos;
			if (pos == start) { printf("0\n"); continue; }
			else if (pos < start) solveL(pos);
			else solveR(pos);
		}
		else {
			int pos, e; cin >> pos >> e; modify(pos, e - 1);
		}
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50