oj.uz

답안 #252075

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252075 2020-07-24T05:57:59 Z thecodingwizard 케이크 (CEOI14_cake) C++11
0 / 100
 1059 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+1);
    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;

            A[i] = idx++;
            if (i < a) {
                lft.upd(a-1-i, A[i]);
            } else {
                rht.upd(i-a-1, A[i]);
            }
            for (int x = 9; x <= e; x--) {
                loc[x+1] = loc[x];
            }
            loc[e] = i;
            for (int x = e-1; 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 847 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Correct 142 ms 1208 KB Output is correct
3 Correct 205 ms 1144 KB Output is correct
4 Correct 142 ms 1144 KB Output is correct
5 Runtime error 848 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 897 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 249 ms 1656 KB Output is correct
8 Correct 160 ms 1536 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 859 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 903 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 63 ms 3448 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Runtime error 947 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 938 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 110 ms 6140 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 888 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 24 ms 896 KB Output isn't correct
3 Incorrect 56 ms 1916 KB Output isn't correct
4 Runtime error 905 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 949 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Correct 110 ms 2536 KB Output is correct
7 Correct 93 ms 1504 KB Output is correct
8 Correct 130 ms 2688 KB Output is correct
9 Runtime error 1059 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 915 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 861 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 898 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 925 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)