oj.uz

Submission #914090

# Submission time Handle Problem Language Result Execution time Memory
914090 2024-01-21T02:38:16 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 608 ms 15956 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;
				
			pi p = mp(st.query(i, i), i);
			if (ten.count(p)) ten.erase(p);

			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); ten.erase(prev(end(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 Correct 295 ms 1000 KB Output is correct
2 Incorrect 166 ms 856 KB Output isn't correct
3 Correct 186 ms 1016 KB Output is correct
4 Correct 104 ms 856 KB Output is correct
5 Correct 315 ms 1860 KB Output is correct
6 Incorrect 252 ms 1884 KB Output isn't correct
7 Correct 197 ms 1880 KB Output is correct
8 Correct 114 ms 1884 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 6736 KB Output is correct
2 Incorrect 77 ms 6480 KB Output isn't correct
3 Incorrect 72 ms 6476 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 193 ms 14680 KB Output is correct
6 Correct 166 ms 14696 KB Output is correct
7 Incorrect 121 ms 14808 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 604 KB Output isn't correct
2 Incorrect 23 ms 856 KB Output isn't correct
3 Incorrect 60 ms 3464 KB Output isn't correct
4 Correct 76 ms 3420 KB Output is correct
5 Incorrect 97 ms 852 KB Output isn't correct
6 Incorrect 106 ms 4908 KB Output isn't correct
7 Incorrect 87 ms 1304 KB Output isn't correct
8 Correct 118 ms 6172 KB Output is correct
9 Incorrect 601 ms 15956 KB Output isn't correct
10 Incorrect 318 ms 1616 KB Output isn't correct
11 Incorrect 393 ms 2872 KB Output isn't correct
12 Correct 608 ms 13404 KB Output is correct
13 Correct 532 ms 15860 KB Output is correct