oj.uz

Submission #252053

# Submission time Handle Problem Language Result Execution time Memory
252053 2020-07-24T04:17:43 Z thecodingwizard Cake (CEOI14_cake) C++11
0 / 100
 1299 ms 13304 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() {
    int n, a; cin >> n >> a; --a;
    int A[n];
    int idx[10];
    lft.init(a+1); rht.init(n-a+1);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        if (A[i] >= n-9) {
            idx[A[i]-(n-9)] = 1000000*(A[i]-(n-10));
            A[i] = 1000000*(A[i]-(n-10));
        }
        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 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[10-e];
            if (i < a) {
                lft.upd(a-1-i, A[i]);
            } else {
                rht.upd(i-a-1, A[i]);
            }
        } 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 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 415 ms 4984 KB Output isn't correct
2 Correct 412 ms 4984 KB Output is correct
3 Incorrect 402 ms 4984 KB Output isn't correct
4 Correct 408 ms 4984 KB Output is correct
5 Incorrect 434 ms 5456 KB Output isn't correct
6 Incorrect 450 ms 5844 KB Output isn't correct
7 Incorrect 447 ms 5752 KB Output isn't correct
8 Correct 442 ms 6008 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 4216 KB Output isn't correct
2 Incorrect 346 ms 4188 KB Output isn't correct
3 Incorrect 334 ms 4088 KB Output isn't correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Incorrect 434 ms 8312 KB Output isn't correct
6 Incorrect 438 ms 8440 KB Output isn't correct
7 Incorrect 423 ms 8440 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 888 KB Output isn't correct
2 Incorrect 91 ms 888 KB Output isn't correct
3 Incorrect 176 ms 2552 KB Output isn't correct
4 Incorrect 177 ms 2424 KB Output isn't correct
5 Incorrect 265 ms 1932 KB Output isn't correct
6 Incorrect 329 ms 3960 KB Output isn't correct
7 Incorrect 371 ms 2552 KB Output isn't correct
8 Incorrect 251 ms 4884 KB Output isn't correct
9 Incorrect 1299 ms 13304 KB Output isn't correct
10 Incorrect 867 ms 5568 KB Output isn't correct
11 Incorrect 926 ms 6508 KB Output isn't correct
12 Incorrect 1121 ms 11768 KB Output isn't correct
13 Incorrect 1155 ms 13176 KB Output isn't correct