Submission #490179

#	Time	Username	Problem	Language	Result	Execution time	Memory
490179		SirCovidThe19th	Cake (CEOI14_cake)	C++17	0 / 100	731 ms	6856 KiB

cake

#include <bits/stdc++.h>
using namespace std;

template<int sz> struct DS{
    int seg[sz * 2];
    void upd(int i, int v){
        seg[i += sz] = v;
        for (i /= 2; i; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]); 
    }
    int qry(int l, int r){ 
        int ans = 0;
        for (l += sz, r += sz; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) ans = max(ans, seg[l++]);
            if (r % 2 == 0) ans = max(seg[r--], ans);
        }
        return ans;
    }
    int walk(int v){
        int i = 1; 
        while (i < sz) i = (seg[i * 2] < v) ? i * 2 + 1 : i * 2;
        return i - sz - 1;
    }
}; 

const int mN = 2.5e5 + 5, mQ = 5e5 + 5;

int n, a, q, rnk[mN]; pair<int, int> tmp[mN]; DS<(1 << 19)> L, R;

int main(){
    cin >> n >> a;  

    for (int i = 1; i <= n; i++) cin >> tmp[i].first, tmp[i].second = i;
    sort(tmp + 1, tmp + n + 1);

    for (int i = 1; i <= n; i++) rnk[i] = ((i >= n - 9) ? mQ * (i - n + 10) : i);
    for (int i = 1; i <= n; i++){
        int pos = tmp[i].second;
        if (pos < a) L.upd(a - pos, rnk[i]);
        if (pos > a) R.upd(pos - a, rnk[i]);
    }

    cin >> q; L.upd(a, 1e9); R.upd(n - a + 1, 1e9);
    while (q--){
        int pos; char type; cin >> type >> pos;
        if (type == 'E'){
            int e; cin >> e;
            if (pos < a) L.upd(a - pos, ++rnk[n - e + 1]);
            if (pos > a) R.upd(pos - a, ++rnk[n - e + 1]);
        }
        else{
            int ans = pos;
            if (pos < a) ans = R.walk(L.qry(1, a - pos)) + a;
            if (pos > a) ans = a - L.walk(R.qry(1, pos - a));
            cout<<abs(pos - ans)<<"\n";
        }
    }
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50