oj.uz

Submission #101150

# Submission time Handle Problem Language Result Execution time Memory
101150 2019-03-17T06:27:26 Z square1001 Cake (CEOI14_cake) C++14
100 / 100
 327 ms 4024 KB 
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 1012345678;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, A, Q;
	cin >> N >> A; --A;
	vector<int> d(N);
	for (int i = 0; i < N; ++i) cin >> d[i];
	vector<int> L = { 1 }, R = { 1 };
	string first = "left";
	function<void(int)> set_first = [&](int pos) {
		if (pos == A) return;
		string last = (L.size() != R.size() ? (L.size() > R.size() ? "left" : "right") : (first == "left" ? "right" : "left"));
		if (pos < A) {
			bool erasure = false;
			while (!L.empty() && L.back() >= A - pos) L.pop_back(), erasure = true;
			if (!erasure && last == "left") return;
			L.push_back(A - pos);
			if (L.size() == 1) first = "right";
			while (R.size() > L.size() + (first == "right" ? 0 : -1)) R.pop_back();
		}
		if (pos > A) {
			bool erasure = false;
			while (!R.empty() && R.back() >= pos - A) R.pop_back(), erasure = true;
			if (!erasure && last == "right") return;
			R.push_back(pos - A);
			if (R.size() == 1) first = "left";
			while (L.size() > R.size() + (first == "left" ? 0 : -1)) L.pop_back();
		}
	};
	vector<int> ip(N);
	for (int i = 0; i < N; ++i) ip[d[i] - 1] = i;
	for (int i = 0; i < N; ++i) {
		set_first(ip[i]);
	}
	int S = min(N, 10);
	vector<int> first_ten(S);
	for (int i = N - 1; i >= N - S; --i) {
		first_ten[N - i - 1] = ip[i];
	}
	cin >> Q;
	for (int i = 0; i < Q; ++i) {
		string tp;
		cin >> tp;
		if (tp == "E") {
			int pos, e;
			cin >> pos >> e; --pos;
			int f = S - 1;
			for (int j = 0; j < S; ++j) {
				if (first_ten[j] == pos) {
					f = j;
				}
			}
			for (int j = f; j >= e; --j) {
				first_ten[j] = first_ten[j - 1];
			}
			first_ten[e - 1] = pos;
			for (int j = e - 1; j >= 0; --j) {
				set_first(first_ten[j]);
			}
		}
		if (tp == "F") {
			int pos;
			cin >> pos; --pos;
			int ans = 0;
			if (pos < A) {
				int ptr = lower_bound(L.begin(), L.end(), A - pos + 1) - L.begin() - 1;
				int rlim = (first == "left" ? ptr - 1 : ptr);
				ans = (A - pos) + (rlim + 1 == R.size() ? N - A : R[rlim + 1]) - 1;
			}
			if (pos > A) {
				int ptr = lower_bound(R.begin(), R.end(), pos - A + 1) - R.begin() - 1;
				int llim = (first == "right" ? ptr - 1 : ptr);
				ans = (pos - A) + (llim + 1 == L.size() ? A + 1 : L[llim + 1]) - 1;
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:75:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     ans = (A - pos) + (rlim + 1 == R.size() ? N - A : R[rlim + 1]) - 1;
                        ~~~~~~~~~^~~~~~~~~~~
cake.cpp:80:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     ans = (pos - A) + (llim + 1 == L.size() ? A + 1 : L[llim + 1]) - 1;
                        ~~~~~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 8 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 504 KB Output is correct
2 Correct 156 ms 384 KB Output is correct
3 Correct 190 ms 464 KB Output is correct
4 Correct 159 ms 508 KB Output is correct
5 Correct 221 ms 512 KB Output is correct
6 Correct 327 ms 688 KB Output is correct
7 Correct 204 ms 632 KB Output is correct
8 Correct 183 ms 632 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1656 KB Output is correct
2 Correct 67 ms 1596 KB Output is correct
3 Correct 45 ms 1656 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 86 ms 2976 KB Output is correct
6 Correct 73 ms 2936 KB Output is correct
7 Correct 65 ms 2808 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 472 KB Output is correct
2 Correct 19 ms 512 KB Output is correct
3 Correct 36 ms 896 KB Output is correct
4 Correct 46 ms 888 KB Output is correct
5 Correct 80 ms 632 KB Output is correct
6 Correct 67 ms 1400 KB Output is correct
7 Correct 69 ms 952 KB Output is correct
8 Correct 89 ms 1284 KB Output is correct
9 Correct 263 ms 3884 KB Output is correct
10 Correct 251 ms 1524 KB Output is correct
11 Correct 223 ms 1788 KB Output is correct
12 Correct 259 ms 3608 KB Output is correct
13 Correct 320 ms 4024 KB Output is correct