Submission #37134

#	Time	Username	Problem	Language	Result	Execution time	Memory
37134		cheater2k	Cake (CEOI14_cake)	C++14	100 / 100	566 ms	14112 KiB

cake

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

const int N = 250005;
int n, q, start, d[N];
vector<int> topten;

struct SegmentTree {
	int T[N << 2]; // maxpos
	SegmentTree() {
		memset(T, 0, sizeof T);
	}
	
	#define mid ((l + r) >> 1)
	void build(int v, int l, int r) {
		if (l == r) { T[v] = l; return; }
		build(v << 1, l, mid); build(v << 1 | 1, mid + 1, r);
		if (d[T[v << 1]] > d[T[v << 1 | 1]]) T[v] = T[v << 1];
		else T[v] = T[v << 1 | 1];
	}
	void upd(int v, int l, int r, int pos) {
		if (l > r || l > pos || r < pos) return;
		if (l == r) { T[v] = pos; return; }
		upd(v << 1, l, mid, pos); upd(v << 1 | 1, mid + 1, r, pos);
		if (d[T[v << 1]] > d[T[v << 1 | 1]]) T[v] = T[v << 1];
		else T[v] = T[v << 1 | 1];
	}
	int get(int v, int l, int r, int L, int R) {
		if (l > r || R < l || L > r) return 0;
		if (L <= l && r <= R) return T[v];
		int le = get(v << 1, l, mid, L, R), ri = get(v << 1 | 1, mid + 1, r, L, R);
		return d[le] > d[ri] ? le : ri;
	} 
	int get_lef(int v, int l, int r, int x) {
		// get the leftmost position i such that i > start and d[i] > x
		if (r <= start) return n + 1;
		if (l > start) {
			if (d[T[v]] <= x) return n + 1;
			if (l == r) {
				if (d[T[v]] > x) return l; else return n + 1;
			}
		}
		int le = get_lef(v << 1, l, mid, x);
		if (le == n + 1) return get_lef(v << 1 | 1, mid + 1, r, x);
		return le;
	}
	int get_rig(int v, int l, int r, int x) {
		// get the rightmost position such that i < start and d[i] > x
		if (l >= start) return 0;
		if (r < start) {
			if (d[T[v]] <= x) return 0;
			if (l == r) {
				if (d[T[v]] > x) return l; else return 0;
			}
		}
		int ri = get_rig(v << 1 | 1, mid + 1, r, x);
		if (ri == 0) return get_rig(v << 1, l, mid, x);
		return ri;
	}
	#undef mid
} seg1, seg2;

int count(int p) {
	if (p == start) return 0;
	// [le+1...ri-1]
	if (p < start) {
		int le = seg1.get(1, 1, n, p, start - 1);
		int ri = seg2.get_lef(1, 1, n, d[le]);
		return ri - p - 1;
	} else { // p > start
		int ri = seg2.get(1, 1, n, start + 1, p);
		int le = seg1.get_rig(1, 1, n, d[ri]);
		return p - le - 1;
	}
}

int main() {
	// freopen("in", "r", stdin);
	// freopen("out", "w", stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> start; // start eating
	for (int i = 1; i <= n; ++i) cin >> d[i];
	seg1.build(1, 1, n);
	seg2.build(1, 1, n);

	// init: stack<int> topten
	priority_queue < pair<int,int> > pq;
	for (int i = 1; i <= n; ++i) pq.push(make_pair(d[i], i));
	while(pq.size() && topten.size() < 10) {
		int p = pq.top().second; pq.pop(); topten.push_back(p);
	}
	// topten contains the ten largest elements in descending order

	cin >> q;
	for (int i = 1; i <= q; ++i) {
		char type; cin >> type;
		if (type == 'E') {
			int pos, e; cin >> pos >> e; // e-th largest element
			vector<int>::iterator it = find(topten.begin(), topten.end(), pos);
			if (it != topten.end()) topten.erase(it);

			for (int i = 0; i < e-1; ++i) d[topten[i]]++;
			topten.insert(topten.begin() + e - 1, pos);
			while(topten.size() > 10) topten.pop_back();

			if (e != topten.size()) d[pos] = d[topten[e]] + 1;
			else if (e != 1) d[pos] = d[topten[e - 2]] - 1;
			else d[pos] = 1; // in case N = 1

			// update
			if (pos < start) seg1.upd(1, 1, n, pos);
			else seg2.upd(1, 1, n, pos);
		} else {
			int pos; cin >> pos;
			printf("%d\n", count(pos));
		}
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:106:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (e != topten.size()) d[pos] = d[topten[e]] + 1;
          ^

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