제출 #413632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413632		sinamhdv	케이크 (CEOI14_cake)	C++11	100 / 100	1470 ms	23020 KiB

cake

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 250100
// Q limit = 500100 ///////////////////////////

int n, st, q;
int a[MAXN];
set<pii> s;
int seg[4 * MAXN];

void build(int v = 1, int l = 0, int r = n - 1)
{
	//FOR(i, 0, n) seg[i] = a[i];

	if (l == r)
	{
		seg[v] = a[l];
		return;
	}
	int mid = (r + l) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}

void add(int i, int x, int v = 1, int l = 0, int r = n - 1)
{
//	seg[i] += x;
	if (l == r)
	{
		seg[v] += x;
		return;
	}
	int mid = (r + l) / 2;
	if (i <= mid) add(i, x, 2 * v, l, mid);
	else add(i, x, 2 * v + 1, mid + 1, r);
	seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}

int getmax(int L, int R, int v = 1, int l = 0, int r = n - 1)
{
/*	int mx = 0;
	FOR(i, L, R + 1) mx = max(mx, seg[i]);
	return mx;*/

	if (l > R || r < L) return 0;
	if (l >= L && r <= R) return seg[v];
	int mid = (r + l) / 2;
	return max(getmax(L, R, 2 * v, l, mid), getmax(L, R, 2 * v + 1, mid + 1, r));
}

int findlpos(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
	/*int res = -1;
	FOR(i, L, R + 1) if (seg[i] > x) res = max(res, i);
	return res;*/

	if (l > R || r < L || seg[v] <= x) return -1;
	if (l == r) return l;
	int mid = (r + l) / 2;
	int pos = findlpos(L, R, x, 2 * v + 1, mid + 1, r);
	if (pos < 0) return findlpos(L, R, x, 2 * v, l, mid);
	return pos;
}

int findrpos(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
	/*int res = n;
	FOR(i, L, R + 1) if (seg[i] > x) return i;
	return res;*/

	if (l > R || r < L || seg[v] <= x) return n;
	if (l == r) return l;
	int mid = (r + l) / 2;
	int pos = findrpos(L, R, x, 2 * v, l, mid);
	if (pos >= n) return findrpos(L, R, x, 2 * v + 1, mid + 1, r);
	return pos;
}

int32_t main(void)
{
	fast_io;
	cin >> n >> st;
	st--;
	FOR(i, 0, n) cin >> a[i], s.insert({a[i], i});

	build();

	cin >> q;
	while (q--)
	{
		char op;
		cin >> op;
		if (op == 'E')	// update
		{
			int i, x;
			cin >> i >> x;
			i--;
			vector<int> tmp;
			FOR(i, 0, x - 1)
			{
				tmp.pb(s.rbegin() -> sc);
				add(tmp.back(), 1);
				a[tmp.back()]++;
				s.erase(--s.end());
			}
			int cur;
			if (x > 1) cur = getmax(tmp.back(), tmp.back()) - 1;
			else cur = getmax(s.rbegin() -> sc, s.rbegin() -> sc) + 1;
			s.erase({a[i], i});
			add(i, cur - a[i]);
			a[i] = cur;
			s.insert({a[i], i});
			for (int u : tmp) s.insert({a[u], u});
		}
		else	// ask
		{
			int i;
			cin >> i;
			i--;
			if (i < st)
			{
				int mx = getmax(i, st - 1);
				int pos = findrpos(st + 1, n - 1, mx);	// upper_bound
				cout << pos - i - 1 << endl;
			}
			else if (i > st)
			{
				int mx = getmax(st + 1, i);
				int pos = findlpos(0, st - 1, mx);	// handle st == 0 //////////////////////////////////////
				cout << i - pos - 1 << endl;
			}
			else
			{
				cout << "0\n";
			}
		}
	}
	return 0;
}

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