제출 #987443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987443		LOLOLO	Cake (CEOI14_cake)	C++17	100 / 100	446 ms	17500 KiB

cake

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 10;
const int lim = N * 2;
int v[N];

struct seg{
    vector <int> st;
    int N;
    void ass(int n) {
        N = n;
        st.assign(n * 4 + 10, 0);
    }

    void upd(int id, int l, int r, int p, int v) {
        if (l > p || r < p)
            return;

        if (l == r) {
            st[id] = v;
            return;
        }

        int m = (l + r) / 2;
        upd(id * 2, l, m, p, v);
        upd(id * 2 + 1, m + 1, r, p, v);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

    int range(int id, int l, int r, int u, int v) {
        if (l > v || r < u)
            return 0;

        if (l >= u && r <= v) {
            return st[id];
        }

        int m = (l + r) / 2;
        return max(range(id * 2, l, m, u, v), range(id * 2 + 1, m + 1, r, u, v));
    }

    int find(int id, int l, int r, int v) {
        if (st[id] < v)
            return r + 1;

        if (l == r)
            return l;

        int m = (l + r) / 2;
        if (st[id * 2] >= v) 
            return find(id * 2, l, m, v);

        return find(id * 2 + 1, m + 1, r, v);
    }

    void upd(int a, int b) {
        upd(1, 1, N, a, b);
    }

    int find(int v) {
        return find(1, 1, N, v);
    }
} L, R;

int a, n;
void change(int x, int b) {
    v[x] = b;
    if (x > a) {
        R.upd(x - a + 1, b);
    }

    if (x < a) {
        L.upd(a - x + 1, b);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> a;

    int st = n + 1;
    L.ass(n);
    R.ass(n);

    vector <int> pos;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        if (n - v[i] < 10)
            pos.pb(i);
    }

    sort(all(pos), [&] (int x, int y) {return v[x] > v[y];});
    for (int j = 0; j < sz(pos); j++)
        v[pos[j]] = lim - j;

    for (int i = 1; i <= n; i++) {
        change(i, v[i]);
    }

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        char ch;
        cin >> ch;

        if (ch == 'E') {
            int p, e;
            cin >> p >> e;

            auto it = find(all(pos), p);
            if (it != pos.end()) {
                pos.erase(it);
            }

            pos.insert(pos.begin() + e - 1, p);
            if (sz(pos) > 10) {
                change(pos.back(), st);
                st++;
                pos.pop_back();
            }

            for (int j = 0; j < sz(pos); j++) {
                change(pos[j], lim - j);
            }
        } else {
            int b;
            cin >> b;

            if (a == b) {
                cout << 0 << '\n';
                continue;
            }

            if (a < b) {
                int mx = R.range(1, 1, n, 1, b - a + 1);
                cout << min(L.find(mx) - 1, a) + b - a - 1 << '\n';
            } else {
                int mx = L.range(1, 1, n, 1, a - b + 1);
                cout << min(R.find(mx) - 1, n - a + 1) + a - b - 1 << '\n';
            }
        }
    }

    //cout << R.find(L.range(1, 1, n, 1, 2)) << '\n';

    return 0;
}

/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/ 

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