Submission #257767

#	Time	Username	Problem	Language	Result	Execution time	Memory
257767		doowey	Cake (CEOI14_cake)	C++14	35 / 100	2100 ms	4088 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 * 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 ask(int node, int cl, int cr, int tl, int tr){
    if(cr < tl)
        return 0;
    if(cl > tr)
        return 0;
    if(cl >= tl && cr <= tr)
        return tree[node];
    int mid = (cl + cr) / 2;
    return max(ask(node * 2, cl, mid, tl, tr), ask(node * 2 + 1, mid + 1, cr, tl, tr));
}

int getrng(int node, int cl, int cr, int tl, int tr, int mode, int vlx){
    if(tl > tr || tree[node] < vlx)
        return -1;
    if(cr < tl)
        return -1;
    if(cl > tr)
        return -1;
    if(cl >= tl && cr <= tr){
        if(cl==cr){
            if(tree[node] < vlx) return -1;
            return cl;
        }
        if(mode == 0){ // to left
            int mid = (cl + cr) / 2;
            if(tree[node * 2] > vlx)
                return getrng(node * 2, cl, mid, tl, tr, mode, vlx);
            if(tree[node * 2 + 1] > vlx)
                return getrng(node * 2 + 1, mid + 1, cr, tl, tr,mode, vlx);
            return -1;
        }
        else{
            int mid = (cl + cr) / 2;
            if(tree[node * 2 + 1] > vlx){
                return getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
            }
            if(tree[node * 2] > vlx)
                return getrng(node * 2, cl, mid, tl, tr, mode, vlx);
            return -1;
        }
    }
    int mid = (cl + cr) / 2;
    int f1,f2;
    if(mode == 0){
        f1 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
        if(f1 != -1) return f1;
        f2 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
        return f2;
    }
    else{
        f1 = getrng(node * 2 + 1, mid + 1, cr, tl, tr, mode, vlx);
        if(f1 != -1) return f1;
        f2 = getrng(node * 2, cl, mid, tl, tr, mode, vlx);
        return f2;
    }
}


int main(){
    fastIO;
    int n, st;
    cin >> n >> st;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        upd(1, 1, n, 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(1, 1, n, st + 1, nx);
                ly = getrng(1,1,n,1,st-1,1,mx);
                if(ly == -1) ly = 0;
                res += st - ly - 1;
            }
            else if(nx < st){
                res += st - nx;
                mx = ask(1, 1, n,nx, st - 1);
                ly = getrng(1,1,n,st+1,n,0,mx);
                if(ly == -1) ly = n + 1;
                res += ly - st - 1;
            }
            cout << res - 1 << "\n";
        }
        else{
            cin >> nx >> mx;
            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;
                    upd(1, 1, n, nx, pp);
                    niw.push_back(nx);
                }
                sz = niw.size();
                pp = nw - sz;
                upd(1, 1, n, cc[p], pp);
                niw.push_back(cc[p]);
            }
            cc = niw;
        }
    }
    return 0;
}

Compilation message (stderr)

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

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