제출 #914093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914093		NK_	케이크 (CEOI14_cake)	C++17	0 / 100	601 ms	15904 KiB

cake

// 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; --e;
				
			pi p = mp(st.query(i, i), i);
			if (ten.count(p)) ten.erase(p);

			assert(sz(ten) >= e);

			set<int> add; int nx = st.query(1, N);
			for(int t = 0; t < e; t++) {
				int x, idx; tie(x, idx) = *rbegin(ten); ten.erase(prev(end(ten)));
				st.upd(idx, nx + e - t + 1);
				add.insert(idx);
			}

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

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

			while(sz(ten) > 10) ten.erase(begin(ten));

			// for(int x = 0; x <= N+1; x++) cout << x << " => " << st.query(x, x) << endl;
		}
	}

	exit(0-0);
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50