oj.uz

Submission #130805

# Submission time Handle Problem Language Result Execution time Memory
130805 2019-07-16T06:04:53 Z lyc Cake (CEOI14_cake) C++14
100 / 100
 985 ms 25592 KB 
#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.find({root->qmax(I,I), I});
            if (it != s.end()) s.erase(it);

            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 (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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 16 ms 1400 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 1220 KB Output is correct
2 Correct 282 ms 1400 KB Output is correct
3 Correct 331 ms 1400 KB Output is correct
4 Correct 180 ms 1400 KB Output is correct
5 Correct 539 ms 2692 KB Output is correct
6 Correct 442 ms 2808 KB Output is correct
7 Correct 364 ms 2780 KB Output is correct
8 Correct 203 ms 2680 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 10488 KB Output is correct
2 Correct 101 ms 10216 KB Output is correct
3 Correct 85 ms 10172 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 204 ms 24524 KB Output is correct
6 Correct 187 ms 24440 KB Output is correct
7 Correct 149 ms 24244 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 752 KB Output is correct
2 Correct 41 ms 888 KB Output is correct
3 Correct 95 ms 5300 KB Output is correct
4 Correct 124 ms 5220 KB Output is correct
5 Correct 144 ms 888 KB Output is correct
6 Correct 193 ms 6884 KB Output is correct
7 Correct 149 ms 1832 KB Output is correct
8 Correct 225 ms 9720 KB Output is correct
9 Correct 985 ms 25592 KB Output is correct
10 Correct 469 ms 1744 KB Output is correct
11 Correct 613 ms 3704 KB Output is correct
12 Correct 948 ms 20728 KB Output is correct
13 Correct 690 ms 25492 KB Output is correct