oj.uz

Submission #914086

# Submission time Handle Problem Language Result Execution time Memory
914086 2024-01-21T02:34:10 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 511 ms 20344 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);
				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 3 ms 500 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 204 ms 4848 KB Output isn't correct
2 Incorrect 159 ms 856 KB Output isn't correct
3 Incorrect 186 ms 1048 KB Output isn't correct
4 Correct 108 ms 1044 KB Output is correct
5 Incorrect 214 ms 4668 KB Output isn't correct
6 Incorrect 206 ms 6484 KB Output isn't correct
7 Incorrect 200 ms 1880 KB Output isn't correct
8 Correct 126 ms 1884 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 6636 KB Output isn't correct
2 Incorrect 76 ms 6484 KB Output isn't correct
3 Incorrect 79 ms 6480 KB Output isn't correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Incorrect 186 ms 14728 KB Output isn't correct
6 Incorrect 178 ms 14672 KB Output isn't correct
7 Incorrect 109 ms 14324 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 712 KB Output isn't correct
2 Incorrect 23 ms 1112 KB Output isn't correct
3 Incorrect 69 ms 3476 KB Output isn't correct
4 Incorrect 58 ms 3408 KB Output isn't correct
5 Incorrect 62 ms 852 KB Output isn't correct
6 Incorrect 102 ms 4956 KB Output isn't correct
7 Incorrect 87 ms 1504 KB Output isn't correct
8 Incorrect 124 ms 6172 KB Output isn't correct
9 Incorrect 511 ms 15772 KB Output isn't correct
10 Incorrect 207 ms 1620 KB Output isn't correct
11 Incorrect 267 ms 2896 KB Output isn't correct
12 Incorrect 456 ms 13392 KB Output isn't correct
13 Incorrect 471 ms 20344 KB Output isn't correct