Submission #933131

#	Time	Username	Problem	Language	Result	Execution time	Memory
933131		Cookie	Cake (CEOI14_cake)	C++14	0 / 100	100 ms	38240 KiB

cake

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod =1e9 + 7;
const int mxn = 250000 + 5, mxq = 1e5 + 5, sq = 300, mxv = 1e4 + 5;
//const int base = (1 <<18);
const ll inf = 3e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
// <3;


struct ST{
    int st[4 * mxn + 1], lz[4 * mxn + 1];
    void init(){
        for(int i = 1; i <= 4 * mxn; i++)lz[i] = -1;
    }
    void push(int nd){
        int &v = lz[nd];
        if(v == -1)return;
        lz[nd << 1] = lz[nd << 1 | 1] = st[nd << 1] = st[nd << 1 | 1] = v;
        v = -1;
    }
    void upd(int nd, int l, int r, int ql, int qr, int v){
        if(ql > r || qr < l)return;
        if(ql <= l && qr >= r){
            lz[nd] = st[nd] = v;
            return;
        }
        int mid = (l + r) >> 1;
        push(nd);
        upd(nd << 1, l, mid, ql, qr, v); upd(nd << 1 | 1, mid + 1, r, ql, qr, v);
    }
    int get(int nd, int l, int r, int id){
        if(l == r)return(st[nd]);
        int mid = (l + r) >> 1;
        push(nd);
        if(id <= mid)return(get(nd << 1, l, mid, id));
        else return(get(nd << 1 | 1, mid + 1, r, id));
    }
};
ST stl, str;
int n, a, q;
int mxid[15], d[mxn + 1], tol[mxn + 1], tor[mxn + 1];
void solve(){
    cin >> n >> a;
    for(int i = 1; i <= n; i++){
        cin >> d[i];
        if(n + 1 - d[i] <= 10){
            mxid[n + 1 - d[i]] = i;
        }
    }
    int lp = a, rp = a;
    tol[a] = tor[a] = a;
    while(lp != 1 || rp != n){
        if(lp == 1){
            rp++; tol[rp] = lp;
        }else if(rp == n){
            lp--; tor[lp] = rp;
        }else if(d[lp - 1] < d[rp + 1]){
            lp--; tor[lp] = rp;
        }else{
            rp++; tol[rp] = lp;
        }
    }
    stl.init(); str.init();
    cin >> q;
    mxid[11] = n + 1;
    for(int i = 1; i <= n; i++){
        str.upd(1, 1, n, i, i, tor[i]);
        stl.upd(1, 1, n, i, i, tol[i]);
    }
    while(q--){

        char c; cin >> c;
        if(c == 'F'){
            int id; cin >> id;
            if(id <= a){
                int idr = str.get(1, 1, n, id);
                cout << idr - id << "\n";
            }else{
                int idl = stl.get(1, 1, n, id);
                cout << id - idl << "\n";
            }
        }else{
            int id, e; cin >> id >> e;
            int val = -1;
            for(int i = 1; i <= 10; i++){
                if(mxid[i] == id){
                    val = i; break;
                }
            }
            if(val == -1){
                for(int j = 10; j >= e + 1; j++){
                    mxid[j] = mxid[j - 1];
                }
                mxid[e] = id;
            }else{
                
                for(int j = val; j >= e + 1; j--)mxid[j] = mxid[j - 1];
                mxid[e] = id;
            }
            if(id == a)continue;
            bool sign = (id > a);
            int atl, atr, atv = e;
            if(sign)atl = stl.get(1, 1, n, id - 1) - 1, atr = id;
            else atr = str.get(1, 1, n, id + 1) + 1, atl = id;
            //for(int i = 1; i <= 10; i++)cout << mxid[i] << " ";
            //cout << "\n";
            while(1){

                if(sign == 0){
                    // ->
                    int idmn = 11, mnv = n + 1;
                    for(int j = atv - 1; j >= 1; j--){
                        if(mxid[j] >= atr && mxid[j] < mnv){
                            idmn = j; mnv = mxid[j];
                        }
                    }

                    stl.upd(1, 1, n, atr, mnv - 1, atl + 1);
                    atr = mnv; atv = idmn;
                    if(atr == n + 1){
                        str.upd(1, 1, n, 1, atl, n);
                        break;
                    }
                }else{
                    //<-
                    int idmx = 11, mxv = 0;
                    for(int j = atv - 1; j >= 1; j--){
                        if(mxid[j] <= atl && mxid[j] > mxv){
                            idmx = j; mxv = mxid[j];
                        }
                    }
                    str.upd(1, 1, n, mxv + 1, atl, atr - 1);
                    atl = mxv; atv = idmx;
                    if(atl == 0){
                        stl.upd(1, 1, n, atr, n, 1);
                        break;
                    }
                }
                sign = !sign;
            }

        }

    }

}


signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("SODOCLA.INP", "r", stdin);
    //freopen("SODOCLA.INP", "w", stdout);
    int tt; tt = 1;
    while(tt--){
        solve();

    }
    return(0);
}
/*
10 5
2 3 4 5 6
*/

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