답안 #933112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933112 2024-02-25T06:03:41 Z Cookie 케이크 (CEOI14_cake) C++14
0 / 100
2000 ms 32212 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 = 2e5 + 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[11], 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;

            for(int i = e + 1; i <= n; i++){
                mxid[i] = mxid[i - 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), atr = id;
            else atr = str.get(1, 1, n, id + 1), atl = id;

            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 + 1, 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 - 1, 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
*/

Compilation message

cake.cpp: In function 'void solve()':
cake.cpp:86:12: warning: array subscript 11 is above array bounds of 'int [11]' [-Warray-bounds]
   86 |     mxid[11] = n + 1;
      |     ~~~~~~~^
cake.cpp:61:5: note: while referencing 'mxid'
   61 | int mxid[11], d[mxn + 1], tol[mxn + 1], tor[mxn + 1];
      |     ^~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 14940 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 319 ms 15656 KB Output isn't correct
2 Incorrect 625 ms 16040 KB Output isn't correct
3 Incorrect 36 ms 15196 KB Output isn't correct
4 Execution timed out 2025 ms 16944 KB Time limit exceeded
5 Execution timed out 2021 ms 19652 KB Time limit exceeded
6 Incorrect 1503 ms 16076 KB Output isn't correct
7 Incorrect 849 ms 15816 KB Output isn't correct
8 Execution timed out 2036 ms 16076 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 15964 KB Output isn't correct
2 Incorrect 50 ms 17452 KB Output isn't correct
3 Incorrect 45 ms 17248 KB Output isn't correct
4 Incorrect 3 ms 14940 KB Output isn't correct
5 Execution timed out 2051 ms 16780 KB Time limit exceeded
6 Execution timed out 2074 ms 16732 KB Time limit exceeded
7 Runtime error 26 ms 32092 KB Execution killed with signal 11
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 15196 KB Output isn't correct
2 Incorrect 8 ms 15196 KB Output isn't correct
3 Incorrect 332 ms 15752 KB Output isn't correct
4 Incorrect 38 ms 15708 KB Output isn't correct
5 Incorrect 5 ms 15196 KB Output isn't correct
6 Incorrect 311 ms 15936 KB Output isn't correct
7 Incorrect 10 ms 15196 KB Output isn't correct
8 Incorrect 1046 ms 16328 KB Output isn't correct
9 Runtime error 32 ms 32212 KB Execution killed with signal 11
10 Incorrect 4 ms 15392 KB Output isn't correct
11 Incorrect 36 ms 15452 KB Output isn't correct
12 Incorrect 1320 ms 16836 KB Output isn't correct
13 Execution timed out 2071 ms 16712 KB Time limit exceeded