답안 #37275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37275 2017-12-23T10:05:26 Z aome 케이크 (CEOI14_cake) C++14
0 / 100
449 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) { // 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);
		}
	}
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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)
# 결과 실행 시간 메모리 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)