Submission #285997

#	Time	Username	Problem	Language	Result	Execution time	Memory
285997		caoash	Cake (CEOI14_cake)	C++14	100 / 100	651 ms	10360 KiB

cake

#pragma GCC target ("avx,avx2")
#pragma GCC optimize ("Ofast")

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

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

template<class T, int SZ> struct Seg{
    T tree[4*SZ];
    T merge(T a, T b){
        return max(a, b);
    }
    
    void update(int v, int l, int r, int i, T x) {
        if (i > r || i < l) {
            return;
        } else if (l == r) {
            tree[v] = x;
        } else {
            int m = (l + r) / 2;
            update(2 * v + 1, l, m, i, x);
            update(2 * v + 2, m + 1, r, i, x);
            tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
        }
    }

    T query2(int v, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) {
            return 0;
        }
        if (l >= ql && r <= qr) {
            return tree[v];
        }
        else {
            int m = (l + r) / 2;
            T a = query2(2 * v + 1, l, m, ql, qr);
            T b = query2(2 * v + 2, m + 1, r, ql, qr);
            return merge(a, b);
        }
    }

    T query(int v, int l, int r, int val, int dir) {
        if (r < l || tree[v] <= val) {
            return -1;
        }
        else if(l == r) {
            // cout << "DONE: " << l << "\n";
            return l;
        }
        else {
            int m = (l + r) / 2;
            // cout << "v, l, r, dir: " << tree[2 * v + 1] << " " << v << " " << l << " " << r << '\n';
            if (dir) {
                if (tree[2 * v + 2] > val) { 
                    return query(2 * v + 2, m + 1, r, val, dir);
                }
                else {
                    return query(2 * v + 1, l, m, val, dir);
                }
            }
            else {
                if (tree[2 * v + 1] > val) {
                    return query(2 * v + 1, l, m, val, dir); 
                }
                else {
                    return query(2 * v + 2, m + 1, r, val, dir);
                }
            }
        }
    }
};

const int MX = 250005;

int pos[MX];

Seg<int, MX> lft, rgt; 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a; cin >> n >> a;
    a--;
    vi d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i]; 
        pos[d[i]] = i;
        if(i < a) lft.update(0, 0, n - 1, i, d[i]);
        else if (i > a) rgt.update(0, 0, n - 1, i, d[i]);
    }
    /*
    cout << "vals: " << '\n';
    for (int i = 0; i < n; i++) {
        cout << vals.query(0, 0, n - 1, i, i) << " ";
    }
    cout << '\n';
    */ 
    int q; cin >> q;
    vector<pi> top;
    for (int i = max(1, n - 9); i <= n; i++) {
        top.pb(mp(i, pos[i]));
    }
    vector<pi> order;
    while(q--) {
        char qt; cin >> qt; 
        if (qt == 'E') {
            int i, e; cin >> i >> e;
            i--;
            /* 
            cout << "TOP: " << '\n';
            for (pi x : top) {
                cout << x.f << " " << x.s << "\n";
            }
            cout << '\n';
            */ 
            // assert(sz(top) <= 10);
            for (int j = 0; j < e - 1; j++) {
                if (top.back().s != i) {
                    int v = top.back().f; int p = top.back().s;
                    order.pb(mp(v + 1, p));
                    // cout << "ADD" << '\n';
                    if(p < a) lft.update(0, 0, n - 1, p, v + 1);
                    else if(p > a) rgt.update(0, 0, n - 1, p, v + 1);
                    d[p] = v + 1;
                }
                else {
                    j--;
                }
                top.pop_back();
            }
            int prev = d[i];
            // cout << "prev: " << prev << endl;
            d[i] = top.back().f + 1;
            if(i < a) lft.update(0, 0, n - 1, i, top.back().f + 1);
            else if(i > a) rgt.update(0, 0, n - 1, i, top.back().f + 1);
            // cout << "ADD" << " " << top.back().f + 1 << " " << top.back().s << '\n';
            order.pb(mp(top.back().f + 1, i));
            while (!top.empty()) {
                // cout << "ADD: " << top.back().f << " " << top.back().s << '\n';
                if(top.back().f != prev) order.pb(mp(top.back().f, top.back().s));
                top.pop_back(); 
            }
            while (sz(order) > 10) order.pop_back();
            reverse(all(order));
            for (pi x : order) {
                top.pb(x);
            }
            order.clear();
        }
        else {
            // cout << "vals: " << '\n';
            /*
            for (int j = 0; j < n; j++) {
                if (j < a) {
                    cout << lft.query2(0, 0, n - 1, j, j) << " ";
                }
                else if (j == a) {
                    cout << -1 << " ";
                }
                else {
                    cout << rgt.query2(0, 0, n - 1, j, j) << " ";
                }
            }
            */
            // cout << '\n';
            int x; cin >> x;
            x--;
            if (x == a) { 
                cout << 0 << '\n';
                continue;
            }
            int best = 0;
            if (x < a) best = lft.query2(0, 0, n - 1, x, a - 1);
            else if (x > a) best = rgt.query2(0, 0, n - 1, a + 1, x);
            // cout << "x, a, best: " << x << " " << a << " " << best << '\n';
            if (x < a) {
                int ans = rgt.query(0, 0, n - 1, best, 0);
                if (rgt.query2(0, 0, n - 1, a + 1, n - 1) <= best) {
                    ans = n;
                }
                // cout << "ans: " << ans << '\n';
                cout << (ans - x - 1) << '\n';
            }
            else if(x > a) {
                int ans = lft.query(0, 0, n - 1, best, 1);
                if (lft.query2(0, 0, n - 1, 0, a - 1) <= best) {
                    ans = -1;
                }
                // cout << "ans: " << ans << '\n';
                cout << (x - ans - 1) << '\n';
            }
        }
    }
}

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