Submission #188246

#	Time	Username	Problem	Language	Result	Execution time	Memory
188246		qkxwsm	Cake (CEOI14_cake)	C++14	100 / 100	1307 ms	25968 KiB

cake

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define MAXN 270013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, S, Q;
int loc[3 * MAXN], arr[MAXN];
set<int> vals;

struct segtree
{
    int stor[2 * MAXN];
    void update(int w, int L, int R, int a, int v)
    {
        if (L == R)
        {
            stor[w] = v;
            return;
        }
        int mid = (L + R) >> 1;
        if (a <= mid) update(w << 1, L, mid, a, v);
        else update(w << 1 | 1, mid + 1, R, a, v);
        stor[w] = max(stor[w << 1], stor[w << 1 | 1]);
    }
    int query(int w, int L, int R, int a, int b)
    {
        if (a <= L && R <= b)
        {
            return stor[w];
        }
        int mid = (L + R) >> 1;
        if (b <= mid) return query(w << 1, L, mid, a, b);
        if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
        return max(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
    }
    int get(int sz, int v)
    {
        //find the first index that's >v.
        if (stor[1] <= v) return sz + 1;
        int w = 1, L = 0, R = sz;
        while(L != R)
        {
            int mid = (L + R) >> 1;
            if (stor[w << 1] > v)
            {
                R = mid;
                w = (w << 1);
            }
            else
            {
                L = mid + 1;
                w = (w << 1 | 1);
            }
        }
        return L;
    }
};

segtree lt, rt;

void setval(int pos, int v)
{
    arr[pos] = v;
    loc[v] = pos;
    vals.insert(v);
    if (pos == S) return;
    if (pos < S)
    {
        lt.update(1, 0, S - 1, S - pos - 1, v);
        // cerr << "UPDATE " << S - pos - 1 << ' ' << v << endl;
    }
    if (pos > S)
    {
        rt.update(1, 0, N - S - 2, pos - S - 1, v);
    }
}
//04312
int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> S; S--;
    FOR(i, 0, N)
    {
        cin >> arr[i]; arr[i]--;
        setval(i, arr[i]);
    }
    cin >> Q;
    while(Q--)
    {
        char c;
        cin >> c;
        if (c == 'E')
        {
            int idx, val;
            cin >> idx >> val; idx--; val--;
            vals.erase(arr[idx]);
            //becomes the arr[idx]th most delcious piece.
            vi inds;
            FOR(j, 0, val)
            {
                auto it = prev(vals.end());
                inds.PB(loc[*it]);
                vals.erase(it);
            }
            int x = *vals.rbegin() + 1;
            setval(idx, x);
            x++;
            FORD(i, SZ(inds), 0)
            {
                setval(inds[i], x);
                x++;
            }
        }
        if (c == 'F')
        {
            int idx;
            cin >> idx; idx--;
            if (idx == S)
            {
                cout << "0\n";
                continue;
            }
            if (idx < S)
            {
                int mx = lt.query(1, 0, S - 1, 0, S - idx - 1);
                // cerr << "MX " << mx << endl;
                int go = rt.get(N - S - 2, mx);
                cout << go + (S - idx) << '\n';
            }
            if (idx > S)
            {
                int mx = rt.query(1, 0, N - S - 2, 0, idx - S - 1);
                int go = lt.get(S - 1, mx);
                cout << go + (idx - S) << '\n';
            }
        }
    }
    return 0;
}

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