Submission #257742

#	Time	Username	Problem	Language	Result	Execution time	Memory
257742		doowey	Cake (CEOI14_cake)	C++14	0 / 100	8 ms	1792 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;

int A[N];

int tree[N * 2 + 512];

int lim;
void setid(int x, int v){
    x += lim;
    tree[x] = v;
    x /= 2;
    while(x > 0){
        tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
        x /= 2;
    }
}

int ask(int l, int r){
    int ans = 0;
    l += lim;
    r += lim;
    while(l <= r){
        if(l % 2 == 1) ans = max(ans, tree[l ++ ]);
        if(r % 2 == 0) ans = max(ans, tree[r -- ]);
        l /= 2;
        r /= 2;
    }
    return ans;
}

int main(){
    fastIO;
    int n, st;
    cin >> n >> st;
    vector<int> top(10);
    vector<int> niw;
    lim = n + 2;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        if(n - A[i] > 0){
            top[n-A[i]] = i;
        }
        setid(i, A[i]);
    }
    int q;
    cin >> q;
    int nx;
    int res;
    char typ;
    int mx;
    int ly;
    int li;
    int nw = n;
    int sz;
    int pp;
    for(int i = 1; i <= q; i ++ ){
        cin >> typ;
        if(typ == 'F'){
            cin >> nx;
            res = 1;
            if(nx > st){
                res += nx - st;
                mx = ask(st + 1, nx);
                ly = st;
                for(int lg = 19; lg >= 0; lg -- ){
                    li = ly - (1 << lg);
                    if(li <= 0) continue;
                    if(ask(li, st - 1) < mx){
                        ly = li;
                    }
                }
                res += st - ly;
            }
            else if(nx < st){
                res += st - nx;
                mx = ask(nx, st - 1);
                ly = st;
                for(int lg = 19; lg >= 0 ; lg -- ){
                    li = ly + (1 << lg);
                    if(li > n) continue;
                    if(ask(st + 1, li) < mx){
                        ly = li;
                    }
                }
                res += ly - st;
            }
            cout << res - 1 << "\n";
        }
        else{
            cin >> nx >> mx;
            mx -- ;
            vector<int> niw;
            bool ok = false;
            for(int j = 0; j < 10 ; j ++ ){
                if(top[j] == nx && j == mx){
                    ok = true;
                }
            }
            if(ok) continue; // nothing changes

            for(int j = 0 ; j < 10; j ++ ){
                if(top[j] == nx) continue;
                if(j == mx){
                    sz = niw.size();
                    pp = nw - sz;
                    setid(nx, pp);
                    niw.push_back(nx);
                }
                else{
                    sz = niw.size();
                    pp = nw - sz;
                    setid(top[j], pp);
                    niw.push_back(top[j]);
                }
            }
            top = niw;
        }
    }
    return 0;
}

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