oj.uz

Submission #37279

# Submission time Handle Problem Language Result Execution time Memory
37279 2017-12-23T11:24:58 Z aome Cake (CEOI14_cake) C++14
100 / 100
 579 ms 8880 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7304 KB Output is correct
2 Correct 0 ms 7304 KB Output is correct
3 Correct 0 ms 7304 KB Output is correct
4 Correct 3 ms 7304 KB Output is correct
5 Correct 6 ms 7464 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 7464 KB Output is correct
2 Correct 189 ms 7464 KB Output is correct
3 Correct 216 ms 7464 KB Output is correct
4 Correct 146 ms 7464 KB Output is correct
5 Correct 216 ms 7464 KB Output is correct
6 Correct 196 ms 7464 KB Output is correct
7 Correct 206 ms 7464 KB Output is correct
8 Correct 196 ms 7464 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 8112 KB Output is correct
2 Correct 79 ms 8112 KB Output is correct
3 Correct 83 ms 8112 KB Output is correct
4 Correct 0 ms 7304 KB Output is correct
5 Correct 133 ms 8880 KB Output is correct
6 Correct 139 ms 8880 KB Output is correct
7 Correct 103 ms 8880 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7304 KB Output is correct
2 Correct 43 ms 7304 KB Output is correct
3 Correct 79 ms 7724 KB Output is correct
4 Correct 66 ms 7724 KB Output is correct
5 Correct 99 ms 7304 KB Output is correct
6 Correct 156 ms 8112 KB Output is correct
7 Correct 126 ms 7464 KB Output is correct
8 Correct 119 ms 8112 KB Output is correct
9 Correct 579 ms 8880 KB Output is correct
10 Correct 313 ms 7304 KB Output is correct
11 Correct 463 ms 7464 KB Output is correct
12 Correct 526 ms 8880 KB Output is correct
13 Correct 446 ms 8880 KB Output is correct