Submission #101146

#	Time	Username	Problem	Language	Result	Execution time	Memory
101146		square1001	Cake (CEOI14_cake)	C++14	0 / 100	323 ms	4040 KiB

cake

#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" ? 1 : 0)) 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" ? 1 : 0)) 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 (stderr)

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: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50