Submission #741560

#	Time	Username	Problem	Language	Result	Execution time	Memory
741560		stevancv	Bitaro's travel (JOI23_travel)	C++14	100 / 100	310 ms	36116 KiB

travel

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const ll linf = 1e18;
int l[N][18], r[N][18], logs[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) l[i][0] = 2 * a[i] - a[i - 1];
    for (int j = 1; j < 18; j++) {
        for (int i = 1; i < n - (1 << j) + 1; i++) {
            l[i][j] = max(l[i][j - 1], l[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 0; i < n - 1; i++) r[i][0] = 2 * a[i] - a[i + 1];
    for (int j = 1; j < 18; j++) {
        for (int i = 0; i < n - (1 << j); i++) {
            r[i][j] = min(r[i][j - 1], r[i + (1 << (j - 1))][j - 1]);
        }
    }
    int zz = 0;
    for (int i = 1; i <= n; i++) {
        if ((1 << (zz + 1)) == i) zz += 1;
        logs[i] = zz;
    }
    auto GetLeft = [&] (int p, int q) {
        if (p > q) return 0;
        int o = logs[q - p + 1];
        return max(l[p][o], l[q - (1 << o) + 1][o]);
    };
    auto GetRight = [&] (int p, int q) {
        if (p > q) return 0;
        int o = logs[q - p + 1];
        return min(r[p][o], r[q - (1 << o) + 1][o]);
    };
    int q; cin >> q;
    while (q--) {
        int s; cin >> s;
        if (s >= a[n - 1]) {
            cout << s - a[0] << en;
            continue;
        }
        if (s <= a[0]) {
            cout << a[n - 1] - s << en;
            continue;
        }
        int up = (int)(upper_bound(a.begin(), a.end(), s) - a.begin());
        int lo = up - 1;
        if (a[lo] == s) lo -= 1;
        int uu = 0;
        ll ans = s;
        if (s - a[lo] > a[up] - s) {
            uu = 1;
            ans = -s;
        }
        while (1) {
            if (uu == 0) {
                if (GetLeft(1, lo) <= a[up] || lo == 0) {
                    ans += a[n - 1] - 2 * a[0];
                    cout << ans << en;
                    break;
                }
                int lef = 1, rig = lo, gde = -1;
                while (lef <= rig) {
                    int mid = lef + rig >> 1;
                    if (GetLeft(mid, lo) > a[up]) {
                        lef = mid + 1;
                        gde = mid;
                    }
                    else rig = mid - 1;
                }
                assert(gde != -1);
                ans -= 2 * a[gde];
                uu ^= 1;
                lo = gde - 1;
                continue;
            }
            if (GetRight(up, n - 2) > a[lo] || up == n - 1) {
                ans += 2 * a[n - 1] - a[0];
                cout << ans << en;
                break;
            }
            int lef = up, rig = n - 2, gde = -1;
            while (lef <= rig) {
                int mid = lef + rig >> 1;
                if (GetRight(up, mid) <= a[lo]) {
                    rig = mid - 1;
                    gde = mid;
                }
                else lef = mid + 1;
            }
            assert(gde != -1);
            ans += 2 * a[gde];
            uu ^= 1;
            up = gde + 1;
        }
    }
    return 0;
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:75:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |                     int mid = lef + rig >> 1;
      |                               ~~~~^~~~~
travel.cpp:95:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |                 int mid = lef + rig >> 1;
      |                           ~~~~^~~~~

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