Submission #90741

#	Time	Username	Problem	Language	Result	Execution time	Memory
90741		minhtung0404	Cake (CEOI14_cake)	C++17	100 / 100	488 ms	5504 KiB

cake

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50