oj.uz

Submission #130799

# Submission time Handle Problem Language Result Execution time Memory
130799 2019-07-16T05:45:00 Z lyc Cake (CEOI14_cake) C++14
0 / 100
 904 ms 31976 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.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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 445 ms 5624 KB Output isn't correct
2 Incorrect 270 ms 5664 KB Output isn't correct
3 Incorrect 310 ms 5752 KB Output isn't correct
4 Incorrect 179 ms 5756 KB Output isn't correct
5 Incorrect 493 ms 7448 KB Output isn't correct
6 Incorrect 416 ms 7800 KB Output isn't correct
7 Incorrect 347 ms 7544 KB Output isn't correct
8 Incorrect 194 ms 7800 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 11640 KB Output isn't correct
2 Incorrect 99 ms 11484 KB Output isn't correct
3 Incorrect 85 ms 11512 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 214 ms 27136 KB Output isn't correct
6 Incorrect 190 ms 26952 KB Output isn't correct
7 Incorrect 153 ms 26956 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1144 KB Output isn't correct
2 Incorrect 37 ms 1384 KB Output isn't correct
3 Incorrect 96 ms 6248 KB Output isn't correct
4 Incorrect 112 ms 6276 KB Output isn't correct
5 Incorrect 125 ms 2040 KB Output isn't correct
6 Incorrect 186 ms 8696 KB Output isn't correct
7 Incorrect 141 ms 3448 KB Output isn't correct
8 Incorrect 210 ms 12280 KB Output isn't correct
9 Incorrect 904 ms 31864 KB Output isn't correct
10 Incorrect 416 ms 5428 KB Output isn't correct
11 Incorrect 557 ms 7956 KB Output isn't correct
12 Incorrect 898 ms 26744 KB Output isn't correct
13 Incorrect 665 ms 31976 KB Output isn't correct