Submission #91034

#	Time	Username	Problem	Language	Result	Execution time	Memory
91034		Flying_dragon_02	Cake (CEOI14_cake)	C++14	100 / 100	541 ms	11696 KiB

cake

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 250005;

ii it[2][4 * N];

int n, q, a[N], x, cnt, p[15];

vector<ii> vec;

ii compare(ii b, ii c, int type) {
    if(b.fi > c.fi) swap(b, c);
    if(type == 1) {
        if(b.fi == c.fi)
            return {b.fi, max(b.se, c.se)};
        else
            return c;
    }
    else {
        if(b.fi == c.fi)
            return {b.fi, min(b.se, c.se)};
        else
            return c;
    }
}

void build_tree(int type, int k, int l, int r) {
    if(l == r) {
        it[type][k] = {a[l], l};
        return ;
    }
    int mid = (l + r) / 2;
    build_tree(type, k << 1, l, mid);
    build_tree(type, k << 1 | 1, mid + 1, r);
    if(type == 0)
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1);
    else
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2);
}

void update(int k, int l, int r, int pos, int val, int type) {
    if(r < pos || pos < l) return ;
    if(pos <= l && r <= pos) {
        it[type][k] = {val, l};
        return ;
    }
    int mid = (l + r) >> 1;
    update(k << 1, l, mid, pos, val, type);
    update(k << 1 | 1, mid + 1, r, pos, val, type);
    if(pos < x)
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1);
    else
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2);
}

int get(int k, int l, int r, int L, int R, int type) {
    if(r < L || R < l || L > R) return 0;
    if(L <= l && r <= R)
        return it[type][k].fi;
    int mid = (l + r) >> 1;
    return max(get(k << 1, l, mid, L, R, type), get(k << 1 | 1, mid + 1, r, L, R, type));
}

int climb(int k, int l, int r, int L, int R, int type, int val) {
    if(r < L || R < l || L > R) return -1;
    if(l == r)
        return it[type][k].se;
    int mid = (l + r) >> 1;
    if(type == 0) {
        if(it[type][k << 1 | 1].fi >= val)
            return climb(k << 1 | 1, mid + 1, r, L, R, type, val);
        return climb(k << 1, l, mid, L, R, type, val);
    }
    else {
        if(it[type][k << 1].fi >= val)
            return climb(k << 1, l, mid, L, R, type, val);
        return climb(k << 1 | 1, mid + 1, r, L, R, type, val);
    }
}

void getpos(int pos) {
    int val, po;
    if(pos < x) {
        val = get(1, 1, x - 1, pos, x - 1, 0);
        if(x + 1 <= n) {
            po = climb(1, x + 1, n, x + 1, n, 1, val);
            if(get(1, x + 1, n, x + 1, po, 1) > val)
                cout << abs(po - 1 - pos) << "\n";
            else
                cout << abs(po - pos) << "\n";
            return ;
        }
        else {
            cout << n - pos << "\n";
            return ;
        }
    }
    else {
        val = get(1, x + 1, n, x + 1, pos, 1);
        if(x - 1 >= 1) {
            po = climb(1, 1, x - 1, 1, x - 1, 0, val);
            if(get(1, 1, x - 1, po, x - 1, 0) > val)
                cout << abs(pos - po - 1) << "\n";
            else
                cout << abs(po - pos) << "\n";
            return ;
        }
        else {
            cout << pos - 1 << "\n";
            return ;
        }
    }
    //cout << val << " " << po << " " << pos << "\n";
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    cin >> n >> x;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        vec.pb({a[i], i});
    }
    if(x - 1 >= 1)
        build_tree(0, 1, 1, x - 1);
    if(x + 1 <= n)
        build_tree(1, 1, x + 1, n);
    sort(vec.begin(), vec.end());
    for(int i = n - 1; i >= max(0, n - 11); i--)
        p[n - i] = vec[i].se;
    cnt = n;
    cin >> q;
    while(q--) {
        char c;
        int pos, e;
        cin >> c;
        if(c == 'F') {
            cin >> pos;
            if(pos == x) cout << "0\n";
            else getpos(pos);
        }
        else {
            cin >> pos >> e;
            int lim = min(n, 10);
            for(int i = lim; i >= e + 1; i--) {
                if(p[i] == pos) {
                    lim = i;
                    break;
                }
            }
            for(int i = lim; i >= e + 1; i--)
                p[i] = p[i - 1];
            p[e] = pos;
            for(int i = e; i >= 1; i--) {
                if(p[i] == x) {++cnt; continue;}
                if(p[i] < x)
                    update(1, 1, x - 1, p[i], ++cnt, 0);
                else
                    update(1, x + 1, n, p[i], ++cnt, 1);
            }
        }
    }
}

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