oj.uz

Submission #914096

# Submission time Handle Problem Language Result Execution time Memory
914096 2024-01-21T02:49:16 Z NK_ Cake (CEOI14_cake) C++17
100 / 100
 952 ms 16232 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;
		st.upd(i + 1, x);
		ten.insert(mp(x, i + 1));
	}

	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 + 1, 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 - 1)) 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 - 1);

				// 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 + 1, 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));

			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); ten.erase(mp(x, idx));
				st.upd(idx, nx--);
				add.insert(idx);
			}

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

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

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

	exit(0-0);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 13 ms 1116 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 856 KB Output is correct
2 Correct 202 ms 860 KB Output is correct
3 Correct 247 ms 860 KB Output is correct
4 Correct 134 ms 1044 KB Output is correct
5 Correct 442 ms 1856 KB Output is correct
6 Correct 365 ms 1880 KB Output is correct
7 Correct 276 ms 1880 KB Output is correct
8 Correct 150 ms 1880 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 6992 KB Output is correct
2 Correct 76 ms 6392 KB Output is correct
3 Correct 79 ms 6484 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 176 ms 14752 KB Output is correct
6 Correct 169 ms 14676 KB Output is correct
7 Correct 112 ms 14672 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 600 KB Output is correct
2 Correct 30 ms 856 KB Output is correct
3 Correct 76 ms 3412 KB Output is correct
4 Correct 108 ms 3368 KB Output is correct
5 Correct 125 ms 848 KB Output is correct
6 Correct 141 ms 5204 KB Output is correct
7 Correct 122 ms 1396 KB Output is correct
8 Correct 157 ms 5980 KB Output is correct
9 Correct 897 ms 16232 KB Output is correct
10 Correct 418 ms 1528 KB Output is correct
11 Correct 554 ms 2896 KB Output is correct
12 Correct 952 ms 13832 KB Output is correct
13 Correct 671 ms 15716 KB Output is correct