제출 #230670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230670		arbor	Cake (CEOI14_cake)	C++14	100 / 100	1758 ms	15456 KiB

cake

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define lc (i << 1)
#define rc (i << 1 | 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 250005, LN = 17, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
int N, a, d[MN], Q;
priority_queue<pii> pq;
int t[MN * 3];

void build(int i, int l, int r) {
    if (l == r) {
        t[i] = d[l];
        return;
    }
    int m = (l + r) / 2;
    build(lc, l, m);
    build(rc, m + 1, r);
    t[i] = max(t[lc], t[rc]);
}

void upd(int i, int l, int r, int idx, int val) {
    if (l > idx || r < idx) return;
    if (l == r) {
        d[idx] = val;
        t[i] = val;
        return;
    }
    int m = (l + r) / 2;
    upd(lc, l, m, idx, val);
    upd(rc, m + 1, r, idx, val);
    t[i] = max(t[lc], t[rc]);
}

int qry(int i, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return 0;
    if (l >= ql && r <= qr) return t[i];
    int m = (l + r) / 2;
    return max(qry(lc, l, m, ql, qr), qry(rc, m + 1, r, ql, qr));
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> a;
    for (int i = 1; i <= N; i++) {
        cin >> d[i];
        pq.emplace(d[i], i);
    }
    build(1, 1, N);
    cin >> Q;
    for (int q = 1; q <= Q; q++) {
        char op;
        cin >> op;
        if (op == 'E') {
            int idx, rnk, val = 0;
            cin >> idx >> rnk;
            vector<pii> v;
            for (int i = 0; i < rnk - 1; i++) {
                while (d[pq.top().second] != pq.top().first) pq.pop();
                v.push_back(pq.top());
                pq.pop();
            }
            if (rnk == 1) val = N + q;
            else val = v.back().first;
            upd(1, 1, N, idx, val);
            pq.emplace(val, idx);
            for (pii p : v) {
                upd(1, 1, N, p.second, p.first + 1);
                pq.emplace(p.first + 1, p.second);
            }
        } else {
            int b;
            cin >> b;
            if (b == a) cout << 0 << '\n';
            else if (b < a) {
                int mx = qry(1, 1, N, b, a - 1);
                int l = a, r = N + 1;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (qry(1, 1, N, a + 1, m) > mx) r = m;
                    else l = m + 1;
                }
                cout << l - 1 - b << '\n';
            } else {
                int mx= qry(1, 1, N, a + 1, b);
                int l = 1, r = a;
                while (l < r) {
                    int m = (l + r) / 2;
                    if (qry(1, 1, N, m, a - 1) < mx) r = m;
                    else l = m + 1;
                }
                cout << b - l << '\n';
            }
        }
    }
    return 0;
}

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