Submission #285904

#	Time	Username	Problem	Language	Result	Execution time	Memory
285904		caoash	Cake (CEOI14_cake)	C++14	35 / 100	2087 ms	25464 KiB

cake

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

const int MX = 200005;

map<int, int> pos;

Seg<int, MX> vals; 

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;
        vals.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;
    vi top;
    for (int i = max(1, n - 9); i <= n; i++) {
        top.pb(i);
    }
    while(q--) {
        char qt; cin >> qt; 
        if (qt == 'E') {
            int i, e; cin >> i >> e;
            i--;
            vi order;
            /* 
            cout << "TOP: " << '\n';
            for (int x : top) {
                cout << x << " ";
            }
            cout << '\n';
            */
            for (int j = 0; j < e - 1; j++) {
                if (pos[top.back()] != i) {
                    order.pb(top.back() + 1);
                    vals.update(0, 0, n - 1, pos[top.back()], top.back() + 1);
                    d[pos[top.back()]] = top.back() + 1;
                    pos[top.back() + 1] = pos[top.back()];
                }
                else {
                    j--;
                }
                top.pop_back();
            }
            int prev = d[i];
            // cout << "prev: " << prev << endl;
            d[i] = top.back() + 1;
            vals.update(0, 0, n - 1, i, top.back() + 1);
            order.pb(top.back() + 1);
            pos[top.back() + 1] = i;
            while (!top.empty()) {
                if(top.back() != prev) order.pb(top.back());
                top.pop_back(); 
            }
            reverse(all(order));
            for (int x : order) {
                top.pb(x);
            }
            /*
            cout << "vals: " << '\n';
            for (int j = 0; j < n; j++) {
                cout << d[j] << " ";
            }
            cout << '\n';
            */
        }
        else {
            int x; cin >> x;
            x--;
            if (x == a) { 
                cout << 0 << '\n';
                continue;
            }
            int best = 0;
            if (x < a) best = vals.query(0, 0, n - 1, x, a - 1);
            else if (x > a) best = vals.query(0, 0, n - 1, a + 1, x);
            if (x < a) {
                int lo = a + 1; int hi = n - 1;
                int ans = n;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (vals.query(0, 0, n - 1, a + 1, mid) > best) {
                        ans = mid;
                        hi = mid - 1;
                    }
                    else {
                        lo = mid + 1;
                    }
                }
                cout << (ans - x - 1) << '\n';
            }
            else {
                int lo = 0; int hi = a - 1;
                int ans = -1;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (vals.query(0, 0, n - 1, mid, a - 1) > best) {
                        ans = mid;
                        lo = mid + 1;
                    }
                    else {
                        hi = mid - 1;
                    }
                }
                cout << (x - ans - 1) << '\n';
            }
        }
    }
}

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