oj.uz

Submission #914095

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

			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 0 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 420 ms 1016 KB Output is correct
2 Incorrect 195 ms 1044 KB Output isn't correct
3 Correct 249 ms 1048 KB Output is correct
4 Correct 153 ms 1044 KB Output is correct
5 Correct 440 ms 1992 KB Output is correct
6 Incorrect 371 ms 1884 KB Output isn't correct
7 Correct 267 ms 1884 KB Output is correct
8 Correct 150 ms 1880 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 6552 KB Output is correct
2 Incorrect 64 ms 6544 KB Output isn't correct
3 Incorrect 60 ms 6184 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Correct 170 ms 14872 KB Output is correct
6 Incorrect 173 ms 14700 KB Output isn't correct
7 Incorrect 97 ms 14412 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 820 KB Output isn't correct
3 Incorrect 75 ms 3516 KB Output isn't correct
4 Incorrect 101 ms 3340 KB Output isn't correct
5 Incorrect 138 ms 804 KB Output isn't correct
6 Incorrect 148 ms 4828 KB Output isn't correct
7 Incorrect 122 ms 1364 KB Output isn't correct
8 Correct 168 ms 5972 KB Output is correct
9 Incorrect 983 ms 15976 KB Output isn't correct
10 Incorrect 420 ms 1872 KB Output isn't correct
11 Incorrect 551 ms 2828 KB Output isn't correct
12 Correct 917 ms 13444 KB Output is correct
13 Correct 689 ms 15700 KB Output is correct