제출 #130799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130799		lyc	케이크 (CEOI14_cake)	C++14	0 / 100	904 ms	31976 KiB

cake

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

int N, A, Q;
set<ii,greater<ii> > s;

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 x, int z) {
        if (s == e) { v = z; return; }
        else if (x <= m) l->update(x, z);
        else r->update(x, z);
        v = max(l->v, r->v);
    }

    int qmax(int x, int y) {
        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));
    }

    int qleft(int y, int z) {
        //cout << "QLEFT " << s << " " << e << " :: " << y << " " << z << endl;
        if (s == e) return (v > z ? s : 0);
        else if (y <= m) return l->qleft(y,z);
        else if (y < e) {
            int idx = r->qleft(y,z);
            if (idx == 0) idx = l->qleft(m,z);
            return idx;
        } else {
            if (v <= z) return 0;
            else if (r->v > z) return r->qleft(y,z);
            else return l->qleft(m,z);
        }
    }

    int qright(int x, int z) {
        //cout << "QRIGHT " << s << " " << e << " :: " << x << " " << z << endl;
        if (s == e) return (v > z ? s : N+1);
        if (x > m) return r->qright(x,z);
        else if (x > s) {
            int idx = l->qright(x,z);
            if (idx == N+1) idx = r->qright(m+1,z);
            return idx;
        } else {
            if (v <= z) return N+1;
            else if (l->v > z) return l->qright(x,z);
            else return r->qright(m+1,z);
        }
    }
} *root;

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> A;
    root = new node(1,N);
    FOR(i,1,N){
        int D; cin >> D;
        root->update(i,D);
        s.insert(ii(D,i));
        if (SZ(s) > 10) s.erase(prev(s.end()));
    }

    //FOR(i,1,N){ cout << root->qmax(i,i) << " "; } cout << endl;

    cin >> Q;
    FOR(i,1,Q){
        char T; cin >> T;
        //cout << "QUERY " << T << endl;
        if (T == 'E'){
            int I, E; cin >> I >> E;
            auto it = s.begin();
            FOR(j,1,E-1) it = next(it);
            for (auto jt = s.begin(); jt != it; ) { 
                auto kt = next(jt);
                ii nv = *jt; ++nv.fi;
                s.erase(jt); s.insert(nv);
                root->update(nv.sc, nv.fi);
                jt = kt;
            }
            root->update(I, it->fi+1), s.insert(ii(it->fi+1,I));
            if ((it = s.find({root->qmax(I,I), I})) != s.end()) s.erase(it);
            if (SZ(s) > 10) { s.erase(prev(s.end())); }
        } else {
            int B; cin >> B;
            //cout << "\t\tAAAA " << B << " :: ";
            if (B == A) cout << 0 << '\n';
            else if (B < A) {
                int maxi = root->qmax(B,A-1);
                int idx = root->qright(A+1,maxi);
                //cout << maxi << " " << idx << endl;
                cout << idx-B-1 << '\n';
            } else {
                int maxi = root->qmax(A+1,B);
                int idx = root->qleft(A-1,maxi);
                //cout << maxi << " " << idx << endl;
                cout << B-idx-1 << '\n';
            }
        }

        //FOR(i,1,N) { cout << root->qmax(i,i) << ' '; } cout << endl;
    }
}

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