oj.uz

Submission #914067

# Submission time Handle Problem Language Result Execution time Memory
914067 2024-01-21T02:16:21 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 625 ms 30108 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; --P;

	Seg st; st.init(N);

	set<pi> ten;

	for(int i = 0; i < N; i++) {
		int x; cin >> x;
		if (i != P) {
			st.upd(i, x);
			ten.insert(mp(x, i));
		}
	}

	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; --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 1884 KB Execution killed with signal 11
2 Incorrect 197 ms 5384 KB Output isn't correct
3 Incorrect 224 ms 5396 KB Output isn't correct
4 Incorrect 134 ms 5396 KB Output isn't correct
5 Runtime error 13 ms 3796 KB Execution killed with signal 11
6 Runtime error 8 ms 3676 KB Execution killed with signal 11
7 Incorrect 233 ms 6620 KB Output isn't correct
8 Incorrect 142 ms 7132 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 8020 KB Output isn't correct
2 Incorrect 94 ms 7980 KB Output isn't correct
3 Incorrect 77 ms 7904 KB Output isn't correct
4 Incorrect 1 ms 500 KB Output isn't correct
5 Incorrect 181 ms 17368 KB Output isn't correct
6 Incorrect 228 ms 17272 KB Output isn't correct
7 Incorrect 117 ms 17068 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 1112 KB Output isn't correct
2 Incorrect 25 ms 1236 KB Output isn't correct
3 Incorrect 74 ms 4452 KB Output isn't correct
4 Incorrect 97 ms 4428 KB Output isn't correct
5 Incorrect 107 ms 1880 KB Output isn't correct
6 Incorrect 114 ms 6484 KB Output isn't correct
7 Incorrect 99 ms 3072 KB Output isn't correct
8 Incorrect 133 ms 8532 KB Output isn't correct
9 Incorrect 625 ms 22188 KB Output isn't correct
10 Incorrect 358 ms 5308 KB Output isn't correct
11 Incorrect 434 ms 7508 KB Output isn't correct
12 Incorrect 614 ms 19284 KB Output isn't correct
13 Runtime error 124 ms 30108 KB Execution killed with signal 11