Submission #257788

#	Time	Username	Problem	Language	Result	Execution time	Memory
257788		doowey	Cake (CEOI14_cake)	C++14	100 / 100	541 ms	9848 KiB

cake

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 250010;

struct Segt{
    int tree[N * 4 + 512];
    void upd(int node, int cl, int cr, int pos, int x){
        if(cl == cr){
            tree[node] = x;
            return ;
        }
        int mid = (cl + cr) / 2;
        if(mid >= pos)
            upd(node * 2, cl, mid, pos, x);
        else
            upd(node * 2 + 1, mid + 1, cr, pos, x);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }
    int get(int node, int cl, int cr, int tl, int tr){
        if(cr < tl || cl > tr)
            return 0;
        if(cl >= tl && cr <= tr){
            return tree[node];
        }
        int mid = (cl + cr) / 2;
        return max(get(node * 2, cl, mid, tl, tr), get(node * 2 + 1, mid + 1, cr, tl, tr));
    }
    int fin(int node, int cl, int cr, int vlx, int mode){
        if(tree[node] < vlx)
            return -1;
        if(cl == cr)
            return cl;
        int mid = (cl + cr) / 2;
        if(mode == 0){
            if(tree[node * 2 + 1] > vlx) return fin(node * 2 + 1, mid + 1, cr, vlx, mode);
            return fin(node * 2, cl, mid, vlx, mode);
        }
        else{
            if(tree[node * 2] > vlx) return fin(node * 2, cl, mid, vlx, mode);
            return fin(node * 2 + 1, mid + 1, cr, vlx, mode);
        }
    }
};

int start;
int n;

Segt Li, Ri;

void setpos(int id, int x){
    if(id < start){
        Li.upd(1, 1, n, id, x);
    }
    else if(id > start){
        Ri.upd(1, 1, n, id, x);
    }
}

int A[N];
int csh[10];
int nov[10];

int main(){
    fastIO;
    cin >> n >> start;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        setpos(i, A[i]);
        if(n - A[i] <= 9)
            csh[n - A[i]] = i;
    }
    for(int i = 1; i <= n; i ++ )
        if(csh[i] == 0) csh[i] = -1;
    int q;
    cin >> q;
    char typ;
    int qq;
    int res;
    int ff;
    int mx;
    int pp;
    int lim = n;
    int id;
    for(int i = 1; i <= q; i ++ ){
        cin >> typ;
        if(typ == 'F'){
            cin >> qq;
            if(qq == start) cout << 0 << "\n";
            else{
                res = 1;
                if(qq > start){
                    res += qq - start;
                    mx = Ri.get(1, 1, n, start + 1, qq);
                    ff = Li.fin(1, 1, n, mx, 0);
                    if(ff == -1) ff = 0;
                    res += start - ff - 1;
                }
                else if(qq < start){
                    res += start - qq;
                    mx = Li.get(1, 1, n, qq, start - 1);
                    ff = Ri.fin(1, 1, n, mx, 1);
                    if(ff == -1) ff = n + 1;
                    res += ff - start - 1;
                }
                cout << res - 1 << "\n";
            }
        }
        else{
            cin >> pp >> qq;
            qq -- ;
            if(csh[qq] == pp) continue;
            lim += 10;
            id = 0;
            for(int y = 0; y < 10; y ++ ){
                if(csh[y] == -1) break;
                if(csh[y] == pp) continue;
                if(y == qq){
                    setpos(pp, lim - id);
                    nov[id++] = pp;
                }
                setpos(csh[y], lim - id);
                nov[id++] = csh[y];
            }
            for(int y = 0; y < 10; y ++ )
                if(csh[y] != -1)
                    csh[y] = nov[y];
        }
    }
    return 0;
}

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