Submission #933123

# Submission time Handle Problem Language Result Execution time Memory
933123 2024-02-25T06:29:29 Z Cookie Cake (CEOI14_cake) C++14
0 / 100
275 ms 26452 KB
#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++){
        if(i <= a)str.upd(1, 1, n, i, i, tor[i]);
        else 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 = e + 1; j <= min(n, 10); j++){
                    mxid[j] = mxid[j - 1];
                }
                mxid[e] = id;
            }else{
                for(int j = e + 1; j <= val; 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
*/
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 14680 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 19124 KB Output isn't correct
2 Incorrect 83 ms 18760 KB Output isn't correct
3 Incorrect 134 ms 19028 KB Output isn't correct
4 Incorrect 96 ms 18352 KB Output isn't correct
5 Incorrect 183 ms 17176 KB Output isn't correct
6 Incorrect 139 ms 19540 KB Output isn't correct
7 Incorrect 159 ms 19548 KB Output isn't correct
8 Incorrect 107 ms 19536 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 16464 KB Output isn't correct
2 Incorrect 37 ms 16472 KB Output isn't correct
3 Incorrect 34 ms 16468 KB Output isn't correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 66 ms 21280 KB Output is correct
6 Incorrect 62 ms 21580 KB Output isn't correct
7 Incorrect 56 ms 21604 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 15196 KB Output isn't correct
2 Incorrect 20 ms 15196 KB Output isn't correct
3 Incorrect 39 ms 15840 KB Output isn't correct
4 Incorrect 40 ms 15964 KB Output isn't correct
5 Incorrect 48 ms 16212 KB Output isn't correct
6 Incorrect 74 ms 16724 KB Output isn't correct
7 Incorrect 63 ms 16716 KB Output isn't correct
8 Correct 92 ms 16976 KB Output is correct
9 Incorrect 275 ms 26452 KB Output isn't correct
10 Incorrect 165 ms 19560 KB Output isn't correct
11 Incorrect 171 ms 20308 KB Output isn't correct
12 Incorrect 262 ms 25428 KB Output isn't correct
13 Incorrect 203 ms 26448 KB Output isn't correct