oj.uz

Submission #252100

# Submission time Handle Problem Language Result Execution time Memory
252100 2020-07-24T06:51:45 Z thecodingwizard Cake (CEOI14_cake) C++11
100 / 100
 686 ms 13308 KB 
#include <bits/stdc++.h>

using namespace std;

struct SegTree {
    int n;
    vector<int> st;
    void init(int _n) {
        n = _n;
        st.assign(4*n, 0);
    }
    void upd(int p, int i, int j, int k, int v) {
        if (k < i || k > j) return;
        if (i == j) {
            st[p] = v;
        } else {
            upd(p << 1, i, (i+j)/2, k, v);
            upd((p << 1) + 1, (i+j)/2+1, j, k, v);
            st[p] = max(st[p*2],st[p*2+1]);
        }
    }
    void upd(int p, int v) {
        upd(1, 0, n-1, p, v);
    }
    int qry(int p, int i, int j, int L, int R) {
        if (R < i || L > j) return 0;
        if (L <= i && j <= R) return st[p];
        return max(qry(p << 1, i, (i+j)/2, L, R), qry((2*p+1), (i+j)/2+1, j, L, R));
    }
    int qry(int i, int j) {
        return qry(1, 0, n-1, i, j);
    }
    int qry2(int p, int i, int j, int mx) {
        if (i == j) {
            if (st[p] > mx) return i;
            return -1;
        }
        if (st[p] <= mx) return -1;
        if (st[p*2] > mx) return qry2(p << 1, i, (i+j)/2, mx);
        return qry2(p*2+1, (i+j)/2+1, j, mx);
    }
    int qry2(int mx) {
        int res = qry2(1, 0, n-1, mx);
        assert(res != -1);
        return res;
    }
} lft, rht;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    int n, a; cin >> n >> a; --a;
    int A[n];
    int loc[11]; for (int i = 1; i <= 10; i++) loc[i] = -1;
    lft.init(a+1); rht.init(n-a);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        if (A[i] >= n-9) {
            loc[n+1-A[i]] = i;
        }
        if (i < a) {
            lft.upd(a-1-i, A[i]);
        } else if (i > a) {
            rht.upd(i-a-1, A[i]);
        }
    }
    lft.upd(a, 1e9);
    rht.upd(n-a-1, 1e9);
    int idx = n+1;
    int q; cin >> q;
    for (int qi = 0; qi < q; qi++) {
        char c; cin >> c;
        if (c == 'E') {
            int i, e; cin >> i >> e; --i;

            for (int x = 10; x >= 1; x--) {
                if (loc[x] == i) {
                    for (int y = x; y <= 9; y++) {
                        loc[y] = loc[y+1];
                    }
                    break;
                }
            }

            for (int x = 9; x >= e; x--) {
                loc[x+1] = loc[x];
            }
            loc[e] = i;
            for (int x = 10; x >= 1; x--) {
                int l = loc[x];
                if (l == -1) continue;
                if (l < a) lft.upd(a-1-l, idx++);
                else if (l > a) rht.upd(l-a-1, idx++);
                A[l] = idx-1;
            }
        } else {
            int b; cin >> b; --b;
            if (b == a) cout << 0 << "\n";
            else {
                if (b < a) {
                    int mx = lft.qry(0,a-1-b);
                    int idx = rht.qry2(mx);
                    cout << a-b+idx << "\n";
                } else {
                    int mx = rht.qry(0,b-a-1);
                    int idx = lft.qry2(mx);
                    cout << b-a+idx << "\n";
                }
            }
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 12 ms 768 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 4984 KB Output is correct
2 Correct 494 ms 632 KB Output is correct
3 Correct 605 ms 632 KB Output is correct
4 Correct 558 ms 512 KB Output is correct
5 Correct 665 ms 5496 KB Output is correct
6 Correct 645 ms 5864 KB Output is correct
7 Correct 635 ms 884 KB Output is correct
8 Correct 627 ms 880 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4216 KB Output is correct
2 Correct 68 ms 4088 KB Output is correct
3 Correct 61 ms 2680 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 120 ms 8312 KB Output is correct
6 Correct 115 ms 8312 KB Output is correct
7 Correct 108 ms 5740 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 888 KB Output is correct
2 Correct 44 ms 512 KB Output is correct
3 Correct 95 ms 1656 KB Output is correct
4 Correct 94 ms 2424 KB Output is correct
5 Correct 116 ms 1784 KB Output is correct
6 Correct 181 ms 2140 KB Output is correct
7 Correct 180 ms 1144 KB Output is correct
8 Correct 323 ms 2304 KB Output is correct
9 Correct 686 ms 13308 KB Output is correct
10 Correct 378 ms 5112 KB Output is correct
11 Correct 467 ms 6392 KB Output is correct
12 Correct 653 ms 11768 KB Output is correct
13 Correct 610 ms 13304 KB Output is correct