제출 #792459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792459		vjudge1	Bitaro's travel (JOI23_travel)	C++17	100 / 100	1089 ms	40836 KiB

travel

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;

using namespace std;

int n;
long long inf = 1e18;
long long a[N];
long long t[N][20];
long long L[N];

long long get(int l, int r)
{
    int g = L[r - l + 1];
    return max(t[l][g], t[r - (1 << g) + 1][g]);
}

long long go_one(int &l, int&r, int &k)
{
    long long res;
    if (abs(a[k] - a[l - 1]) <= abs(a[k] - a[r + 1])) {
        l--;
        res = abs(a[k] - a[l]);
        k = l;
    } else {
        r++;
        res = abs(a[k] - a[r]);
        k = r;
    }
    return res;
}

long long solve(int k)
{
    int l = k, r = k;
    long long res = 0;
    while (l > 1 || r < n) {
        res += go_one(l, r, k);
        if (l == k) {
            int tl = 1, tr = l;
            while (tl < tr) {
                int tm = (tl + tr) / 2;
                if (get(tm, l - 1) < a[r] - a[l]) {
                    tr = tm;
                } else {
                    tl = tm + 1;
                }
            }
            res += a[l] - a[tl];
            l = k = tl;
        } else {
            int tl = r, tr = n;
            while (tl < tr) {
                int tm = (tl + tr) / 2;
                if (get(r, tm) < a[r] - a[l]) {
                    tl = tm + 1;
                } else {
                    tr = tm;
                }
            }
            res += a[tl] - a[r];
            r = k = tl;
        }
    }
    return res;
}

int main()
{
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = -inf;
    a[n + 1] = inf;

    for (int i = 1; i <= n; i++) {
        t[i][0] = a[i + 1] - a[i];
    }
    for (int i = 2; i < N; i++) {
        L[i] = L[i / 2] + 1;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            t[j][i] = max(t[j][i - 1], t[j + (1 << i - 1)][i - 1]);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        long long x;
        cin >> x;
        int i = lower_bound(a + 1, a + n + 1, x) - a;
        if (i > 1 && abs(a[i - 1] - x) <= abs(a[i] - x)) {
            i--;
        }

        cout << solve(i) + abs(a[i] - x) << "\n";
    }
}

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

travel.cpp: In function 'int main()':
travel.cpp:95:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   95 |             t[j][i] = max(t[j][i - 1], t[j + (1 << i - 1)][i - 1]);
      |                                                    ~~^~~

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