Submission #1299471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299471		vs358	Cake (CEOI14_cake)	C++20	100 / 100	648 ms	47060 KiB

cake

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

#define int long long
#define mp make_pair
#define f first
#define s second
#define INF (LLONG_MAX-100)
typedef pair<int, int> pi;
typedef pair<pi, pi> pipi;
typedef pair<int, pipi> ipipi;
typedef pair<int, pi> ipi;

struct node{
    int s, e, m;
    int val=0, lo=0, hi=0;
    node *l, *r;

    node(int S, int E){
        s = S;
        e = E;
        m = (s+e)/2;
        if(s != e){
            l = new node(s, m);
            r = new node(m+1, e);
        } else {
            l = nullptr;
            r = nullptr;
        }
    }

    void upd(int X, int V){
        if(s == X and e == X){
            val = V;
            lo = V;
            hi = V;
            return;
        }
        if (X <= m) l->upd(X, V);
        else r->upd(X, V);
        lo = min(l->lo, r->lo);
        hi = max(l->hi, r->hi);
    }

    int max_to(int S, int E){
        if(S > E) return 0;
        
        if(s >= S and e <= E) return hi;
        if(E <= m) return l->max_to(S, E);
        else if (S > m) return r->max_to(S, E);
        return max(l->max_to(S, m), r->max_to(m+1, E));
    }

    int find_depth(int V){
        if(hi < V) return e-s+1;
        if(s == e) return 0;

        if(l->hi >= V) return l->find_depth(V);
        return (l->e - l->s + 1) + r->find_depth(V);
    }
} *left_tree, *right_tree;

int de_to_id[6000000];
vector<int> v;
void solve(){
    int n, a;
    cin >> n >> a;

    left_tree = new node(1, max(1ll, a-1));
    right_tree = new node(1, max(n-a, 1ll));

    int arr[n+2];

    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        if(i < a) left_tree->upd(a-i, arr[i]);
        else if (i > a) right_tree->upd(i-a, arr[i]);
        de_to_id[arr[i]] = i; 
        if(n-i <= 9) v.push_back(i);
    } 

    int e_max = min(10ll, n);
    v.resize(e_max);
     
    int q;
    cin >> q;
    stack<int> st;

    while(q--){
        char c;
        cin >> c;
        if(c == 'E'){
            int x, y;
            cin >> x >> y;
            
            int pre = arr[x];
            for(int i = 0; i < y-1; i++){
                if(v.back() == pre){
                    v.pop_back();
                    i--;
                    continue;
                }
                st.push(v.back() + 1);
                v.pop_back();
                de_to_id[st.top()] = de_to_id[st.top()-1];
                int z = de_to_id[st.top()];
                arr[z]++;
                if(z < a) left_tree->upd(a-z, arr[z]);
                else if (z > a) right_tree->upd(z-a, arr[z]);
            }

            int mi = 0;
            if(v.empty()) mi = 1;
            else mi = v.back()+1;

            de_to_id[mi] = x;
            arr[x] = mi;
            if(x < a) left_tree->upd(a-x, arr[x]);
            else if (x > a) right_tree->upd(x-a, arr[x]);


            while(not v.empty()){
                if(v.back() != pre) st.push(v.back());
                v.pop_back();
            }
            v.push_back(mi);
            while(not st.empty()){
                v.push_back(st.top());
                st.pop();
            }
            sort(v.begin(), v.end());

            while(v.size() > 10) {
                v.erase(v.begin()); // Remove smallest value
            }
           
        } else {
            int x;
            cin >> x;
            if(x == a){
                cout << 0 << '\n';
                continue;
            }
            if(x < a){
                //cout << "DEBUG 1: " << left_tree->max_to(1, a-x) << " " << right_tree->find_depth(left_tree->max_to(1, a-x)) << endl;
                if(a == n) cout << a-x << '\n';
                else cout << a-x + right_tree->find_depth(left_tree->max_to(1, a-x)) << '\n';
            } else {
                //cout << "DEBUG 2: " << right_tree->max_to(1, x-a) << " " << left_tree->find_depth(right_tree->max_to(1, x-a)) << endl;
                if(a == 1) cout << x-a << '\n';
                else cout << x-a + left_tree->find_depth(right_tree->max_to(1, x-a)) << '\n';
            }
        }

    }



}

signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    //cin >> t;
    t = 1;
    while(t--){
        solve();
    }
    
}

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