제출 #101431

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101431		lyc	케이크 (CEOI14_cake)	C++14	0 / 100	1732 ms	152684 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; vector<int> v;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2) {
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }

    void def(int i, int x) {
        if (s == e) { v.clear(); v.push_back(x); }
        else if (i <= m) l->def(i, x);
        else r->def(i, x);
    }

    void build() {
        if (s == e) return;
        l->build();
        r->build();
        for (int i = 0, j = 0; i < SZ(l->v) || j < SZ(r->v);) {
            if (i < SZ(l->v) && (j == SZ(r->v) || l->v[i] <= r->v[j])) v.push_back(l->v[i++]);
            else v.push_back(r->v[j++]);
        }

        //cout << s << " " << e << " : ";
        //for (auto x : v) cout << x << " "; cout << endl;
    }

    void update(int i, int ov, int nv) {
        //cout << "UPDATE " << i << " " << nv << endl;
        //cout << '\t'; for (auto y : v) cout << y << " "; cout << endl;
        if (s != e) {
            if (i <= m) l->update(i, ov, nv);
            else r->update(i, ov, nv);
        }
        stack<int> s;
        while (v.back() != ov) {
            s.push(v.back());
            v.pop_back();
            assert(!v.empty());
        }
        v.pop_back();

        while (!s.empty() && s.top() < nv) {
            v.push_back(s.top());
            s.pop();
        }
        v.push_back(nv);
        while (!s.empty()) {
            v.push_back(s.top());
            s.pop();
        }
    }

    void increase(int x) {
        if (s != e) {
            if (l->v.back() >= x) l->increase(x);
            if (r->v.back() >= x) r->increase(x);
        }

        //cout << "INCREASING " << s << " " << e << endl;
        for (int i = SZ(v)-1; i >= 0 && v[i] >= x; --i) {
            ++v[i];
        }
        //cout << '\t'; for (auto y : v) cout <<y << " " ; cout<< endl;
    }

    ll qmax(int x, int y) {
        //cout << "QMAX " << x << " " << y << " of " << s << " " << e << endl;
        if (s == x && e == y) { assert(!v.empty()); return v.back(); }
        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));
    }

    int qcntless(int x, int y, int z) {
        if (s == x && e == y) return lower_bound(ALL(v), z) - v.begin();
        else if (y <= m) return l->qcntless(x, y, z);
        else if (x >  m) return r->qcntless(x, y, z);
        else return l->qcntless(x, m, z) + r->qcntless(m+1, y, z);
    }

    void dbg() {
    }
} *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<int> delival;
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        d[i] *= 500000;
        root->def(i, d[i]);
        delival.insert(d[i]);
    }
    root->build();

    int q; cin >> q;
    for (int qi = 0; qi < q; ++qi) {
        char t; cin >> t;
        if (t == 'F') {
            int b; cin >> b;
            //cout << "HI" << endl;

            if (b == a) cout << 0 << '\n';
            else if (b < a) {
                //cout << "CASE 1: " << endl;
                int maxi = root->qmax(b, a-1);
                //cout << maxi << endl;
                int cnt = root->qcntless(a+1, n, maxi);
                cout << cnt + (a-b) << '\n';
            }
            else {
                int maxi = root->qmax(a+1, b);
                //cout << "MAXI " << maxi << endl;
                int cnt = root->qcntless(1, a-1, maxi);
                cout << cnt + (b-a) << '\n';
            }
        }
        else {
            int i, e; cin >> i >> e;
            //cout << "OVAL " << d[i] << endl;
            //for (auto x : delival) cout << x << " "; cout << endl;

            ll ov = d[i];
            delival.erase(d[i]);

            auto it = delival.end();
            for (it = prev(it); e > 1; --e) {
                auto jt = prev(it);
                delival.insert(*it+1);
                delival.erase(it);
                it = jt;
            }
            //if (d[i] == *it) continue;

            d[i] = *it+1;
            delival.insert(d[i]);

            //cout << "NVAL " << d[i] << endl;
            //for (auto x : delival) cout << x << " "; cout << endl;
            root->increase(d[i]);
            root->update(i, ov, d[i]);
        }

        //cout << flush;
    }
}

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