oj.uz

Submission #914077

# Submission time Handle Problem Language Result Execution time Memory
914077 2024-01-21T02:23:42 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 633 ms 28388 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;

			set<int> add; int nx = 1e9;
			for(int t = 0; t < e; t++) {

				int x, idx; tie(x, idx) = *rbegin(ten);
				st.upd(idx, x + 1); nx = min(nx, x);
				ten.erase(prev(end(ten)));
				add.insert(idx);
			}

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

			if (add.count(i)) add.erase(i);

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

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

	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 Runtime error 4 ms 1624 KB Execution killed with signal 11
2 Incorrect 191 ms 860 KB Output isn't correct
3 Incorrect 215 ms 856 KB Output isn't correct
4 Incorrect 136 ms 1108 KB Output isn't correct
5 Runtime error 9 ms 3420 KB Execution killed with signal 11
6 Runtime error 8 ms 3420 KB Execution killed with signal 11
7 Incorrect 225 ms 1884 KB Output isn't correct
8 Incorrect 142 ms 1888 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 6704 KB Output isn't correct
2 Incorrect 77 ms 6412 KB Output isn't correct
3 Incorrect 75 ms 6540 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 193 ms 14776 KB Output isn't correct
6 Incorrect 178 ms 14692 KB Output isn't correct
7 Incorrect 117 ms 14416 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 604 KB Output isn't correct
2 Incorrect 29 ms 848 KB Output isn't correct
3 Incorrect 62 ms 3324 KB Output isn't correct
4 Incorrect 89 ms 3412 KB Output isn't correct
5 Incorrect 108 ms 848 KB Output isn't correct
6 Incorrect 110 ms 4944 KB Output isn't correct
7 Incorrect 102 ms 1408 KB Output isn't correct
8 Incorrect 126 ms 5968 KB Output isn't correct
9 Incorrect 633 ms 15900 KB Output isn't correct
10 Incorrect 348 ms 1620 KB Output isn't correct
11 Incorrect 428 ms 3008 KB Output isn't correct
12 Incorrect 608 ms 13472 KB Output isn't correct
13 Runtime error 116 ms 28388 KB Execution killed with signal 11