oj.uz

답안 #914078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914078 2024-01-21T02:24:48 Z NK_ 케이크 (CEOI14_cake) C++17
0 / 100
 631 ms 28500 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;
			assert(sz(ten) >= e);

			set<int> add; int nx = 1e9;
			for(int t = 0; t < e; t++) {
				assert(sz(ten));
				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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1628 KB Execution killed with signal 6
2 Incorrect 190 ms 860 KB Output isn't correct
3 Incorrect 211 ms 1500 KB Output isn't correct
4 Incorrect 127 ms 860 KB Output isn't correct
5 Runtime error 9 ms 3420 KB Execution killed with signal 6
6 Runtime error 8 ms 3420 KB Execution killed with signal 6
7 Incorrect 220 ms 1884 KB Output isn't correct
8 Incorrect 135 ms 1884 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 6696 KB Output isn't correct
2 Incorrect 78 ms 6480 KB Output isn't correct
3 Incorrect 82 ms 6480 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 230 ms 14672 KB Output isn't correct
6 Incorrect 175 ms 14676 KB Output isn't correct
7 Incorrect 123 ms 14732 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 600 KB Output isn't correct
2 Incorrect 25 ms 856 KB Output isn't correct
3 Incorrect 66 ms 3448 KB Output isn't correct
4 Incorrect 79 ms 3412 KB Output isn't correct
5 Incorrect 103 ms 664 KB Output isn't correct
6 Incorrect 110 ms 4948 KB Output isn't correct
7 Incorrect 98 ms 1368 KB Output isn't correct
8 Incorrect 127 ms 5968 KB Output isn't correct
9 Incorrect 631 ms 15676 KB Output isn't correct
10 Incorrect 344 ms 1484 KB Output isn't correct
11 Incorrect 425 ms 2856 KB Output isn't correct
12 Incorrect 624 ms 13648 KB Output isn't correct
13 Runtime error 143 ms 28500 KB Execution killed with signal 6