oj.uz

Submission #914080

# Submission time Handle Problem Language Result Execution time Memory
914080 2024-01-21T02:27:15 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 466 ms 28496 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;
			
			ten.erase(mp(st.query(i, i), i));

			assert(sz(ten) >= 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);
				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));
		}
	}

	exit(0-0);
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 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 10 ms 1668 KB Execution killed with signal 6
2 Incorrect 161 ms 1048 KB Output isn't correct
3 Incorrect 183 ms 860 KB Output isn't correct
4 Incorrect 130 ms 1052 KB Output isn't correct
5 Runtime error 76 ms 4688 KB Execution killed with signal 6
6 Runtime error 8 ms 3420 KB Execution killed with signal 6
7 Incorrect 196 ms 1876 KB Output isn't correct
8 Incorrect 136 ms 2136 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 6576 KB Output isn't correct
2 Incorrect 77 ms 6580 KB Output isn't correct
3 Incorrect 72 ms 6484 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 198 ms 15108 KB Output isn't correct
6 Incorrect 169 ms 14672 KB Output isn't correct
7 Incorrect 112 ms 14320 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 860 KB Execution killed with signal 6
2 Incorrect 23 ms 860 KB Output isn't correct
3 Incorrect 63 ms 3416 KB Output isn't correct
4 Incorrect 54 ms 3416 KB Output isn't correct
5 Runtime error 10 ms 860 KB Execution killed with signal 6
6 Incorrect 102 ms 4852 KB Output isn't correct
7 Incorrect 85 ms 1356 KB Output isn't correct
8 Incorrect 120 ms 6224 KB Output isn't correct
9 Incorrect 466 ms 15896 KB Output isn't correct
10 Runtime error 7 ms 856 KB Execution killed with signal 6
11 Runtime error 59 ms 3152 KB Execution killed with signal 6
12 Incorrect 461 ms 13400 KB Output isn't correct
13 Runtime error 116 ms 28496 KB Execution killed with signal 6