Submission #101621

#	Time	Username	Problem	Language	Result	Execution time	Memory
101621		lyc	Cake (CEOI14_cake)	C++14	83.33 / 100	2037 ms	38168 KiB

cake

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

typedef long long ll;
typedef pair<int, int> ii;
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()

struct node {
    int s, e, m, v;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), v(0) {
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }

    void update(int i, int x) {
        if (s == e) { v = x; return; }
        else if (i<=m)l->update(i, x);
        else r->update(i, x);
        v = max(l->v, r->v);
    }

    int qmax(int x, int y) {
        if (x > y) return 0;
        if (s == x && e == y) return v;
        else if (y <= m) return l->qmax(x, y);
        else if (x > m) return r->qmax(x, y);
        else return max(l->qmax(x, m), r->qmax(m+1, y));
    }
} *root;

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a; cin >> n >> a;
    int d[n+1];
    root = new node(1, n);
    set<ii> s;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        root->update(i, d[i]);
        s.insert(ii(d[i], i));
    }

    int q; cin >> q;
    for (int qi = 0; qi < q; ++qi) {
        char t; cin >> t;
        if (t == 'F') {
            int b; cin >> b;
            if (b == a) cout << 0 << '\n';
            else if (b < a) {
                int maxi = root->qmax(b, a-1);
                //int idx = root->qrightidx(a+1, n, maxi);
                int lo = a+1, hi = n+1;
                while (lo < hi) {
                    int mid = (lo+hi)/2;
                    if (root->qmax(a+1, mid) < maxi) lo = mid+1;
                    else hi = mid;
                }
                int idx = hi;

                //cout << "HI " << idx << endl;
                cout << idx-1-b << '\n';
            }
            else {
                int maxi = root->qmax(a+1, b);
                //int idx = root->qleftidx(1, a-1, maxi);
                int lo = 1, hi = a;
                while (lo < hi) {
                    int mid = (lo+hi)/2;
                    if (root->qmax(mid, a-1) < maxi) hi = mid;
                    else lo = mid+1;
                }
                int idx = lo-1;

                //cout << "NO " << idx << endl;
                //cout << "\t" << root->qmax(idx, a-1) << endl;
                cout << b-idx-1 << '\n';
            }
        }
        else {
            int j, e; cin >> j >> e;

            s.erase(ii(d[j], j));
            vector<int> modified;
            for (int i = 0; i < e-1; ++i) {
                int idx = s.rbegin()->sc;
                s.erase(prev(s.end()));
                root->update(idx, d[idx]+1);
                ++d[idx];
                modified.push_back(idx);
            }
            root->update(j, s.rbegin()->fi+1);
            d[j] = s.rbegin()->fi+1;
            modified.push_back(j);

            for (auto x : modified) {
                s.insert(ii(d[x], x));
            }
        }
        //cout << flush;
    }
}

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