oj.uz

Submission #914094

# Submission time Handle Problem Language Result Execution time Memory
914094 2024-01-21T02:46:13 Z NK_ Cake (CEOI14_cake) C++17
0 / 100
 896 ms 16212 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));
		}
	}

	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;
				
			ten.erase(mp(st.query(i, i), i));

			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); ten.erase(mp(x, idx));
				st.upd(idx, nx--);
				add.insert(idx);
			}

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

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

			// 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 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 Correct 407 ms 860 KB Output is correct
2 Incorrect 207 ms 860 KB Output isn't correct
3 Correct 250 ms 860 KB Output is correct
4 Correct 139 ms 860 KB Output is correct
5 Correct 451 ms 1880 KB Output is correct
6 Incorrect 361 ms 1880 KB Output isn't correct
7 Correct 274 ms 1884 KB Output is correct
8 Correct 155 ms 1884 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6548 KB Output is correct
2 Incorrect 79 ms 6668 KB Output isn't correct
3 Incorrect 73 ms 6352 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 170 ms 14804 KB Output is correct
6 Correct 161 ms 14672 KB Output is correct
7 Incorrect 108 ms 14640 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 600 KB Output isn't correct
2 Incorrect 30 ms 852 KB Output isn't correct
3 Incorrect 78 ms 3412 KB Output isn't correct
4 Correct 101 ms 3348 KB Output is correct
5 Incorrect 125 ms 688 KB Output isn't correct
6 Incorrect 134 ms 4944 KB Output isn't correct
7 Incorrect 119 ms 1384 KB Output isn't correct
8 Correct 169 ms 5972 KB Output is correct
9 Incorrect 896 ms 16212 KB Output isn't correct
10 Incorrect 418 ms 1448 KB Output isn't correct
11 Incorrect 556 ms 3156 KB Output isn't correct
12 Correct 858 ms 13644 KB Output is correct
13 Correct 676 ms 15756 KB Output is correct