oj.uz

Submission #252091

# Submission time Handle Problem Language Result Execution time Memory
252091 2020-07-24T06:16:36 Z thecodingwizard Cake (CEOI14_cake) C++11
0 / 100
 936 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];
    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;
            if (i == a) continue;
            if (loc[e] == i) continue;

            for (int x = 9; x <= e; x--) {
                loc[x+1] = loc[x];
            }
            loc[e] = i;
            for (int x = e; x >= 1; x--) {
                int l = loc[x];
                if (l < a) lft.upd(a-1-l, idx++);
                else if (l > a) rht.upd(l-a-1, idx++);
            }
        } 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 1 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 916 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Correct 141 ms 1016 KB Output is correct
3 Incorrect 208 ms 1096 KB Output isn't correct
4 Correct 140 ms 1144 KB Output is correct
5 Runtime error 853 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 876 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 217 ms 1144 KB Output isn't correct
8 Correct 165 ms 1144 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 865 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 864 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 63 ms 2936 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 936 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 895 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 105 ms 5752 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 841 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 23 ms 640 KB Output isn't correct
3 Incorrect 52 ms 1656 KB Output isn't correct
4 Runtime error 859 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 835 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Correct 93 ms 2040 KB Output is correct
7 Correct 88 ms 1016 KB Output is correct
8 Incorrect 119 ms 2356 KB Output isn't correct
9 Runtime error 884 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 844 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 832 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 916 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 883 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)