제출 #916840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916840		thangdz2k7	Bitaro's travel (JOI23_travel)	C++17	15 / 100	3071 ms	35456 KiB

travel

#include <bits/stdc++.h>
#define ll long long


using namespace std;

const int N = 2e5 + 5;

int n, x[N];
int q;

int Max[N][20];
int Min[N][20];
int LG[N];

void prepare(){
    for (int i = n; i >= 1; -- i){
        Max[i][0] = 2 * x[i] - x[i - 1];
        Min[i][0] = 2 * x[i] - x[i + 1];
        for (int j = 1; j < 20; ++ j){
            int u = i + (1 << (j - 1));
            if (u > n) break;
            Max[i][j] = max(Max[i][j - 1], Max[u][j - 1]);
            Min[i][j] = min(Min[i][j - 1], Min[u][j - 1]);
        }
        LG[i] = log2(i);
    }
}

int getmax(int l, int r){
    int lg = LG[r - l + 1];
    return max(Max[l][lg], Max[r - (1 << lg) + 1][lg]);
}

int getmin(int l, int r){
    int lg = LG[r - l + 1];
    return min(Min[l][lg], Min[r - (1 << lg) + 1][lg]);
}

ll calc(int l, int p, int r){
    if (l == 0) return x[n] - p;
    if (r == n + 1) return p - x[1];

    //2 * x - x-1 > r - x

    if (p - x[l] <= x[r] - p){
        // 2 * x[k] - x[k - 1] > x[r];

        int L = 2;
        int R = l - 1;
        int ans = 1;
        while (L <= R){
            int mid = L + R >> 1;
            if (getmax(mid, l - 1) > x[r]){
                ans = mid;
                L = mid + 1;

            }
            else R = mid - 1;
        }

        ans = l;

        return calc(ans - 1, x[ans], r) + p - x[ans];
    }

    // 2 * x[k] - x[k + 1] <= x[l]

    int L = r + 1;
    int R = n - 1;
    int ans = n;
    while (L <= R){
        int mid = L + R >> 1;
        if (getmin(r + 1, mid) <= x[l]){
            R = mid - 1;
            ans = mid;
        }
        else L = mid + 1;
    }

    ans = r;

    return calc(l, x[ans], ans + 1) + x[ans] - p;
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> x[i];
    prepare();

    cin >> q;
    while (q --){
        int k; cin >> k;
        int r = lower_bound(x + 1, x + n + 1, k) - x;
        int l = r - 1;
        if (x[r] == k) ++ r;
        cout << calc(l, k, r) << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

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

travel.cpp: In function 'long long int calc(int, int, int)':
travel.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int mid = L + R >> 1;
      |                       ~~^~~
travel.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid = L + R >> 1;
      |                   ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 55