oj.uz

Submission #90739

# Submission time Handle Problem Language Result Execution time Memory
90739 2018-12-24T08:04:33 Z minhtung0404 Cake (CEOI14_cake) C++17
0 / 100
 624 ms 5436 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;
            for (int i = min(10, n); 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 452 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 230 ms 544 KB Output isn't correct
2 Correct 158 ms 712 KB Output is correct
3 Correct 173 ms 712 KB Output is correct
4 Correct 117 ms 712 KB Output is correct
5 Incorrect 265 ms 872 KB Output isn't correct
6 Correct 227 ms 888 KB Output is correct
7 Correct 195 ms 932 KB Output is correct
8 Correct 124 ms 1068 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2500 KB Output is correct
2 Correct 51 ms 2500 KB Output is correct
3 Correct 47 ms 2500 KB Output is correct
4 Incorrect 2 ms 2500 KB Output isn't correct
5 Correct 82 ms 4212 KB Output is correct
6 Incorrect 79 ms 4380 KB Output isn't correct
7 Correct 62 ms 4380 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 4380 KB Output isn't correct
2 Correct 25 ms 4380 KB Output is correct
3 Correct 51 ms 4380 KB Output is correct
4 Correct 61 ms 4380 KB Output is correct
5 Incorrect 77 ms 4380 KB Output isn't correct
6 Correct 89 ms 4380 KB Output is correct
7 Correct 86 ms 4380 KB Output is correct
8 Correct 97 ms 4380 KB Output is correct
9 Incorrect 624 ms 5420 KB Output isn't correct
10 Incorrect 249 ms 5420 KB Output isn't correct
11 Correct 318 ms 5420 KB Output is correct
12 Correct 441 ms 5420 KB Output is correct
13 Incorrect 366 ms 5436 KB Output isn't correct