oj.uz

Submission #101146

# Submission time Handle Problem Language Result Execution time Memory
101146 2019-03-17T06:20:56 Z square1001 Cake (CEOI14_cake) C++14
0 / 100
 323 ms 4040 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" ? 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

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.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 504 KB Output isn't correct
2 Incorrect 171 ms 504 KB Output isn't correct
3 Incorrect 192 ms 476 KB Output isn't correct
4 Correct 150 ms 384 KB Output is correct
5 Incorrect 239 ms 512 KB Output isn't correct
6 Incorrect 242 ms 608 KB Output isn't correct
7 Incorrect 232 ms 512 KB Output isn't correct
8 Correct 177 ms 512 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 1656 KB Output isn't correct
2 Incorrect 56 ms 1656 KB Output isn't correct
3 Incorrect 45 ms 1528 KB Output isn't correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 78 ms 2936 KB Output isn't correct
6 Incorrect 91 ms 2936 KB Output isn't correct
7 Incorrect 102 ms 2736 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 504 KB Output isn't correct
2 Incorrect 24 ms 460 KB Output isn't correct
3 Incorrect 42 ms 988 KB Output isn't correct
4 Incorrect 62 ms 1016 KB Output isn't correct
5 Incorrect 72 ms 632 KB Output isn't correct
6 Incorrect 91 ms 1400 KB Output isn't correct
7 Incorrect 71 ms 1016 KB Output isn't correct
8 Incorrect 130 ms 1196 KB Output isn't correct
9 Incorrect 302 ms 3936 KB Output isn't correct
10 Incorrect 279 ms 1528 KB Output isn't correct
11 Incorrect 277 ms 1888 KB Output isn't correct
12 Incorrect 323 ms 3576 KB Output isn't correct
13 Incorrect 270 ms 4040 KB Output isn't correct