제출 #439242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439242		BeanZ	케이크 (CEOI14_cake)	C++14	100 / 100	688 ms	18332 KiB

cake

// I_Love_LPL 11m
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 3e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
ll a[N], pos[N], stR[N * 4], stL[N * 4];
ll n;
void updR(ll k, ll l, ll r, ll x, ll v){
    if (x > r || x < l) return;
    ll mid = (l + r) >> 1;
    if (l == r){
        stR[k] = v;
        return;
    }
    updR(k << 1, l, mid, x, v);
    updR(k << 1 | 1, mid + 1, r, x, v);
    stR[k] = max(stR[k << 1], stR[k << 1 | 1]);
}
void updL(ll k, ll l, ll r, ll x, ll v){
    if (x > r || x < l) return;
    ll mid = (l + r) >> 1;
    if (l == r){
        stL[k] = v;
        return;
    }
    updL(k << 1, l, mid, x, v);
    updL(k << 1 | 1, mid + 1, r, x, v);
    stL[k] = max(stL[k << 1], stL[k << 1 | 1]);
}
ll getR(ll k, ll l, ll r, ll x, ll y){
    if (x > r || y < l) return 0;
    if (x <= l && y >= r) return stR[k];
    ll mid = (l + r) >> 1;
    return max(getR(k << 1, l, mid, x, y), getR(k << 1 | 1, mid + 1, r, x, y));
}
ll getL(ll k, ll l, ll r, ll x, ll y){
    if (x > r || y < l) return 0;
    if (x <= l && y >= r) return stL[k];
    ll mid = (l + r) >> 1;
    return max(getL(k << 1, l, mid, x, y), getL(k << 1 | 1, mid + 1, r, x, y));
}
ll getposR(ll k, ll l, ll r, ll v){
    ll mid = (l + r) >> 1;
    if (stR[k] < v) return n + 1;
    if (l == r) return l;
    if (stR[k << 1] >= v) return getposR(k << 1, l, mid, v);
    else return getposR(k << 1 | 1, mid + 1, r, v);
}
ll getposL(ll k, ll l, ll r, ll v){
    ll mid = (l + r) >> 1;
    if (stL[k] < v) return 0;
    if (l == r) return l;
    if (stL[k << 1 | 1] >= v) return getposL(k << 1 | 1, mid + 1, r, v);
    else return getposL(k << 1, l, mid, v);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll d;
    cin >> n >> d;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (i < d) updL(1, 1, d, i, a[i]);
        if (i > d) updR(1, d, n, i, a[i]);
        pos[a[i]] = i;
    }
    ll q;
    cin >> q;
    ll tt = n;
    while (q--){
        char task;
        cin >> task;
        if (task == 'E'){
            ll u, e;
            cin >> u >> e;
            ll id = min(n, 10ll);
            for (int i = 1; i <= id; i++){
                if (pos[n - i + 1] == u){
                    id = i;
                    break;
                }
            }
            for (int i = id; i >= (e + 1); i--){
                pos[n - i + 1] = pos[n - i + 2];
            }
            pos[n - e + 1] = u;
            tt++;
            for (int i = 1; i <= e; i++){
                if (pos[n - i + 1] < d) updL(1, 1, d, pos[n - i + 1], tt - i + 1);
                if (pos[n - i + 1] > d) updR(1, d, n, pos[n - i + 1], tt - i + 1);
            }
        }
        else {
            ll u;
            cin >> u;
            if (u == d) cout << 0 << endl;
            else if (u < d){
                ll mx = getL(1, 1, d, u, d);
                ll id = getposR(1, d, n, mx);
                cout << id - u - 1 << endl;
            } else {
                ll mx = getR(1, d, n, d, u);
                ll id = getposL(1, 1, d, mx);
                cout << u - id - 1 << endl;
            }
        }
    }
}
/*
7 2
3 7 6 5 2 1 4
5
E 5 1
E 6 3
E 6 1
E 1 5
F 4
Ans:

Out:
*/

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In function 'int main()':
cake.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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