Submission #37275

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
37275	2017-12-23T10:05:26 Z	aome	Cake (CEOI14_cake)	C++14	0 / 100	449 ms	8880 KB

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) { // find min pos, max(pos -> start - 1) < val
	if (l >= start || it[i] > val) return start;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = findL(i << 1, l, mid, val);
	if (res != start) return res;
	return findL(i << 1 | 1, mid + 1, r, val);
}

int findR(int i, int l, int r, int val) { // find max pos, max(start + 1 -> pos) < val
	if (r <= start || it[i] > val) return start;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = findR(i << 1 | 1, mid + 1, r, val);
	if (res != start) return res;
	return findR(i << 1, l, mid, 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 mxPos = findR(1, 1, n, mx);
	for (auto i : top10) {
		if (i > start && a[i] > mx) mxPos = min(mxPos, i - 1);
	}
	res += mxPos - start;
	cout << res << '\n';
}

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 mnPos = findL(1, 1, n, mx);
	for (auto i : top10) {
		if (i < start && a[i] > mx) mnPos = max(mnPos, i + 1);
	}
	res += start - mnPos;
	cout << res << '\n';
}

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 < n; ++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) { cout << "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

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	7304 KB	Output is correct
2	Incorrect	0 ms	7304 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	196 ms	7464 KB	Output isn't correct
2	Correct	129 ms	7464 KB	Output is correct
3	Incorrect	173 ms	7464 KB	Output isn't correct
4	Correct	173 ms	7464 KB	Output is correct
5	Incorrect	216 ms	7464 KB	Output isn't correct
6	Correct	166 ms	7464 KB	Output is correct
7	Incorrect	183 ms	7464 KB	Output isn't correct
8	Correct	159 ms	7464 KB	Output is correct

Subtask #3

0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	236 ms	8112 KB	Execution timed out (wall clock limit exceeded)
2	Runtime error	196 ms	8112 KB	Execution timed out (wall clock limit exceeded)
3	Runtime error	189 ms	8112 KB	Execution timed out (wall clock limit exceeded)
4	Correct	0 ms	7304 KB	Output is correct
5	Incorrect	316 ms	8880 KB	Output isn't correct
6	Incorrect	319 ms	8880 KB	Output isn't correct
7	Runtime error	239 ms	8880 KB	Execution timed out (wall clock limit exceeded)

Subtask #4

0.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	63 ms	7304 KB	Output isn't correct
2	Incorrect	53 ms	7304 KB	Output isn't correct
3	Incorrect	259 ms	7724 KB	Output isn't correct
4	Incorrect	196 ms	7724 KB	Output isn't correct
5	Runtime error	263 ms	7304 KB	Execution timed out (wall clock limit exceeded)
6	Incorrect	326 ms	8112 KB	Output isn't correct
7	Runtime error	219 ms	7464 KB	Execution timed out (wall clock limit exceeded)
8	Incorrect	153 ms	8112 KB	Output isn't correct
9	Runtime error	449 ms	8880 KB	Execution timed out (wall clock limit exceeded)
10	Runtime error	309 ms	7304 KB	Execution timed out (wall clock limit exceeded)
11	Runtime error	329 ms	7464 KB	Execution timed out (wall clock limit exceeded)
12	Runtime error	416 ms	8880 KB	Execution timed out (wall clock limit exceeded)
13	Runtime error	439 ms	8880 KB	Execution timed out (wall clock limit exceeded)