oj.uz

Submission #914070

# Submission time Handle Problem Language Result Execution time Memory
914070 2024-01-21T02:18:03 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 627 ms 28500 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 != 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;
					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;
					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; --i;

			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 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 Runtime error 4 ms 1628 KB Execution killed with signal 11
2 Incorrect 192 ms 860 KB Output isn't correct
3 Incorrect 227 ms 1044 KB Output isn't correct
4 Incorrect 138 ms 1044 KB Output isn't correct
5 Runtime error 13 ms 3264 KB Execution killed with signal 11
6 Runtime error 7 ms 3420 KB Execution killed with signal 11
7 Incorrect 231 ms 1884 KB Output isn't correct
8 Incorrect 148 ms 1880 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 6748 KB Output isn't correct
2 Incorrect 75 ms 6456 KB Output isn't correct
3 Incorrect 78 ms 6468 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 238 ms 14716 KB Output isn't correct
6 Incorrect 196 ms 14676 KB Output isn't correct
7 Incorrect 136 ms 14604 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 604 KB Output isn't correct
2 Incorrect 26 ms 848 KB Output isn't correct
3 Incorrect 64 ms 3420 KB Output isn't correct
4 Incorrect 70 ms 3448 KB Output isn't correct
5 Incorrect 109 ms 1104 KB Output isn't correct
6 Incorrect 110 ms 4828 KB Output isn't correct
7 Incorrect 100 ms 1364 KB Output isn't correct
8 Incorrect 127 ms 5964 KB Output isn't correct
9 Incorrect 627 ms 15848 KB Output isn't correct
10 Incorrect 355 ms 1872 KB Output isn't correct
11 Incorrect 431 ms 2896 KB Output isn't correct
12 Incorrect 597 ms 13512 KB Output isn't correct
13 Runtime error 121 ms 28500 KB Execution killed with signal 11