Submission #257753

#	Time	Username	Problem	Language	Result	Execution time	Memory
257753		doowey	Cake (CEOI14_cake)	C++14	0 / 100	2098 ms	6440 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;
    lim = n + 2;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        setid(i, A[i]);
    }
    vector<int> cc;
    for(int j = 0 ; j < 10 ; j ++ ){
        for(int i = 1; i <= n; i ++ ){
            if(n - j == A[i]){
                cc.push_back(i);
                break;
            }
        }
    }
    int q;
    cin >> q;
    int nx;
    int res;
    char typ;
    int mx;
    int ly;
    int li;
    int nw = n;
    int sz;
    int pp;
    vector<int> niw;
    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;
            if(cc[mx] == nx) continue;
            nw += 10;
            niw.clear();
            for(int p = 0 ; p < cc.size(); p ++ ){
                if(cc[p] == nx) continue;
                if(p == mx){
                    sz = niw.size();
                    pp = nw - sz;
                    setid(nx, pp);
                    niw.push_back(nx);
                }
                sz = niw.size();
                pp = nw - sz;
                setid(cc[p], pp);
                niw.push_back(cc[p]);
            }
            cc = niw;
        }
    }
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:111:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int p = 0 ; p < cc.size(); p ++ ){
                             ~~^~~~~~~~~~~

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