oj.uz

Submission #252099

# Submission time Handle Problem Language Result Execution time Memory
252099 2020-07-24T06:49:27 Z thecodingwizard Cake (CEOI14_cake) C++11
0 / 100
 938 ms 1048580 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 = 9; y >= x; 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
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 824 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 479 ms 632 KB Output isn't correct
3 Incorrect 526 ms 512 KB Output isn't correct
4 Correct 457 ms 576 KB Output is correct
5 Runtime error 831 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 825 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 561 ms 888 KB Output isn't correct
8 Correct 562 ms 768 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 864 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 858 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Incorrect 63 ms 2808 KB Output isn't correct
4 Correct 0 ms 384 KB Output is correct
5 Runtime error 885 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 886 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 107 ms 5624 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 837 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 36 ms 512 KB Output isn't correct
3 Incorrect 81 ms 1528 KB Output isn't correct
4 Runtime error 887 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 887 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Incorrect 155 ms 2040 KB Output isn't correct
7 Incorrect 157 ms 1016 KB Output isn't correct
8 Incorrect 302 ms 2364 KB Output isn't correct
9 Runtime error 938 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 853 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 827 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 903 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 885 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)