oj.uz

Submission #914093

# Submission time Handle Problem Language Result Execution time Memory
914093 2024-01-21T02:42:21 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 601 ms 15904 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);
			for(int t = 0; t < e; t++) {
				int x, idx; tie(x, idx) = *rbegin(ten); ten.erase(prev(end(ten)));
				st.upd(idx, nx + e - t + 1);
				add.insert(idx);
			}

			st.upd(i, nx + 1);
			ten.insert(mp(nx + 1, 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 0 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 291 ms 1004 KB Output is correct
2 Incorrect 157 ms 856 KB Output isn't correct
3 Correct 197 ms 860 KB Output is correct
4 Correct 107 ms 1040 KB Output is correct
5 Correct 300 ms 1856 KB Output is correct
6 Incorrect 253 ms 1884 KB Output isn't correct
7 Correct 195 ms 1880 KB Output is correct
8 Correct 111 ms 2080 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 6740 KB Output is correct
2 Incorrect 81 ms 6484 KB Output isn't correct
3 Incorrect 83 ms 6440 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Correct 186 ms 14852 KB Output is correct
6 Correct 166 ms 14840 KB Output is correct
7 Incorrect 112 ms 14416 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 600 KB Output isn't correct
2 Incorrect 26 ms 860 KB Output isn't correct
3 Incorrect 61 ms 3412 KB Output isn't correct
4 Correct 76 ms 3380 KB Output is correct
5 Incorrect 96 ms 784 KB Output isn't correct
6 Incorrect 103 ms 5000 KB Output isn't correct
7 Incorrect 95 ms 1520 KB Output isn't correct
8 Correct 123 ms 5956 KB Output is correct
9 Incorrect 601 ms 15904 KB Output isn't correct
10 Incorrect 322 ms 1620 KB Output isn't correct
11 Incorrect 415 ms 2992 KB Output isn't correct
12 Correct 574 ms 13396 KB Output is correct
13 Correct 548 ms 15900 KB Output is correct