oj.uz

Submission #914084

# Submission time Handle Problem Language Result Execution time Memory
914084 2024-01-21T02:32:25 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 41316 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair

#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;

struct Seg {
	const int ID = 0; int comb(int a, int b) { return max(a, b); }

	vi seg; int N; void init(int n) {
		for(N = 1; N < n; N *= 2);
		seg.assign(2*N, ID);
	}

	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }

	void upd(int p, int x) {
		seg[p += N] = x; for(p /= 2; p; p /= 2) pull(p);
	}

	int query(int l, int r) {
		int ra = 0, rb = 0;
		for(l += N, r += N + 1; l < r; l /= 2, r /= 2) {
			if (l & 1) ra = comb(seg[l++], ra);
			if (r & 1) rb = comb(rb, seg[--r]);
		}
		return comb(ra, rb);
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
		
	int N, P; cin >> N >> P;

	Seg st; st.init(N + 2);

	set<pi> ten;

	st.upd(0, 1e9); st.upd(N + 1, 1e9);
	for(int i = 0; i < N; i++) {
		int x; cin >> x;
		if ((i+1) != P) {
			st.upd(i + 1, x);
			ten.insert(mp(x, i + 1));
		}
	}

	while(sz(ten) > 10) ten.erase(begin(ten));

	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		char c; cin >> c;
		if (c == 'F') {
			int x; cin >> x;

			if (x == P) cout << 0 << nl;
			else if (x > P) {
				int mx = st.query(P, x);

				// find first mx > st.query(mid, P)
				int lo = 0, hi = P;
				while(lo < hi) {
					int mid = (lo + hi) / 2;
					// cout << mid << " => " << st.query(mid, P) << endl;
					if (mx > st.query(mid, P)) hi = mid;
					else lo = mid + 1;
				}	
				
				// cout << "Q1: " << lo << " " << x << endl;

				cout << x - lo << nl;
			} else if (x < P) {
				int mx = st.query(x, P);

				// find lst where mx > st.query(P, mid)
				int lo = P, hi = N + 1;
				while(lo < hi) {
					int mid = (lo + hi + 1) / 2;
					// cout << mid << " => " << st.query(P, mid) << endl;
					if (mx > st.query(P, mid)) lo = mid;
					else hi = mid - 1;
				}

				// cout << "Q2: " << lo << " " << x << endl;

				cout << lo - x << nl;
			}
		} else {
			int i, e; cin >> i >> e; --e;
			
			ten.erase(mp(st.query(i, i), i));

			assert(sz(ten) >= e);

			set<int> add; int nx = st.query(1, N) + 1;
			for(int t = 0; t < e; t++) {
				int x, idx; tie(x, idx) = *rbegin(ten);
				st.upd(idx, x + 1); nx = min(nx, x);
				add.insert(idx);
			}

			st.upd(i, nx);
			ten.insert(mp(nx, i));

			for(auto& idx : add) ten.insert(mp(st.query(idx, idx), idx));

			while(sz(ten) > 10) ten.erase(begin(ten));


			for(int x = 0; x <= N+1; x++) cout << x << " => " << st.query(x, x) << endl;
		}
	}

	exit(0-0);
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 23332 KB Time limit exceeded
2 Execution timed out 2071 ms 23116 KB Time limit exceeded
3 Execution timed out 2035 ms 22464 KB Time limit exceeded
4 Execution timed out 2059 ms 23856 KB Time limit exceeded
5 Execution timed out 2041 ms 26048 KB Time limit exceeded
6 Execution timed out 2013 ms 26044 KB Time limit exceeded
7 Execution timed out 2013 ms 26196 KB Time limit exceeded
8 Execution timed out 2037 ms 26340 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 31088 KB Time limit exceeded
2 Execution timed out 2023 ms 31540 KB Time limit exceeded
3 Execution timed out 2066 ms 32048 KB Time limit exceeded
4 Incorrect 1 ms 344 KB Output isn't correct
5 Execution timed out 2093 ms 41316 KB Time limit exceeded
6 Execution timed out 2025 ms 39764 KB Time limit exceeded
7 Execution timed out 2090 ms 41300 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 21972 KB Time limit exceeded
2 Execution timed out 2033 ms 22560 KB Time limit exceeded
3 Execution timed out 2050 ms 28756 KB Time limit exceeded
4 Execution timed out 2073 ms 28948 KB Time limit exceeded
5 Execution timed out 2044 ms 21304 KB Time limit exceeded
6 Execution timed out 2047 ms 30176 KB Time limit exceeded
7 Execution timed out 2061 ms 23032 KB Time limit exceeded
8 Execution timed out 2084 ms 32264 KB Time limit exceeded
9 Execution timed out 2078 ms 41152 KB Time limit exceeded
10 Execution timed out 2067 ms 21820 KB Time limit exceeded
11 Execution timed out 2032 ms 24496 KB Time limit exceeded
12 Execution timed out 2052 ms 38484 KB Time limit exceeded
13 Execution timed out 2043 ms 40628 KB Time limit exceeded