oj.uz

Submission #90741

# Submission time Handle Problem Language Result Execution time Memory
90741 2018-12-24T08:17:43 Z minhtung0404 Cake (CEOI14_cake) C++17
100 / 100
 488 ms 5504 KB 
#include<bits/stdc++.h>
const int N = 250005;
using namespace std;

int n, st, a[N], q, last[20], it[N << 2], cnt;

void init(int i, int l, int r){
    if (l == r){
        it[i] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    init(i << 1, l, mid); init(i << 1 | 1, mid+1, r);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void update(int i, int l, int r, int pos, int val){
    if (l > pos || pos > r) return;
    if (l == r){
        it[i] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, pos, val); update(i << 1 | 1, mid+1, r, pos, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

int get(int i, int l, int r, int L, int R){
    if (L > r || l > R) return -1;
    if (L <= l && r <= R) return it[i];
    int mid = (l + r) >> 1;
    return max(get(i << 1, l, mid, L, R), get(i << 1 | 1, mid+1, r, L, R));
}

int rig(int i, int l, int r, int pos, int val){
    if (r < pos) return -1;
    if (it[i] < val) return -1;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = rig(i << 1, l, mid, pos, val);
    if (ans == -1) ans = rig(i << 1 | 1, mid+1, r, pos, val);
    return ans;
}

int lef(int i, int l, int r, int pos, int val){
    if (l > pos) return -1;
    if (it[i] < val) return -1;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = lef(i << 1 | 1, mid+1, r, pos, val);
    if (ans == -1) ans = lef(i << 1, l, mid, pos, val);
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> st;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > n-10) last[n-a[i]+1] = i;
    }
    init(1, 1, n); cnt = n;
    cin >> q;
    while (q--){
        char c; int pos, e;
        cin >> c;
        if (c == 'E'){
            cin >> pos >> e;
            int cur = min(n, 10);
            for (int i = 1; i <= 10; i++) if (last[i] == pos) cur = i;
            for (int i = cur; i > e; i--) last[i] = last[i-1];
            last[e] = pos;
            for (int i = e; i >= 1; i--) {
                a[last[i]] = ++cnt;
                update(1, 1, n, last[i], a[last[i]]);
            }
        }
        else{
            cin >> pos;
            if (pos == st) {
                cout << 0 << "\n";
                continue;
            }
            int Max, ans;
            if (pos < st){
                Max = get(1, 1, n, pos, st-1);
                ans = rig(1, 1, n, st+1, Max);
                if (ans == -1) ans = n;
                else ans--;
                ans = abs(pos - ans);
            }
            else{
                Max = get(1, 1, n, st+1, pos);
                ans = lef(1, 1, n, st-1, Max);
                if (ans == -1) ans = 1;
                else ans++;
                ans = abs(pos - ans);
            }
            cout << ans << "\n";
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 9 ms 860 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 924 KB Output is correct
2 Correct 156 ms 924 KB Output is correct
3 Correct 179 ms 1104 KB Output is correct
4 Correct 116 ms 1104 KB Output is correct
5 Correct 274 ms 1104 KB Output is correct
6 Correct 234 ms 1168 KB Output is correct
7 Correct 203 ms 1180 KB Output is correct
8 Correct 124 ms 1180 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2716 KB Output is correct
2 Correct 54 ms 2716 KB Output is correct
3 Correct 47 ms 2732 KB Output is correct
4 Correct 2 ms 2732 KB Output is correct
5 Correct 78 ms 4412 KB Output is correct
6 Correct 74 ms 4412 KB Output is correct
7 Correct 63 ms 4412 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4412 KB Output is correct
2 Correct 24 ms 4412 KB Output is correct
3 Correct 47 ms 4412 KB Output is correct
4 Correct 59 ms 4412 KB Output is correct
5 Correct 80 ms 4412 KB Output is correct
6 Correct 88 ms 4412 KB Output is correct
7 Correct 91 ms 4412 KB Output is correct
8 Correct 103 ms 4412 KB Output is correct
9 Correct 488 ms 5468 KB Output is correct
10 Correct 251 ms 5468 KB Output is correct
11 Correct 320 ms 5468 KB Output is correct
12 Correct 430 ms 5468 KB Output is correct
13 Correct 366 ms 5504 KB Output is correct