Submission #1165487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165487		antonn	Bitaro's travel (JOI23_travel)	C++20	0 / 100	19 ms	584 KiB

travel

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5 + 7;
const int L = 20;

int a[N], lg[N];
pi rmq[L][N];

int get_min(int l, int r) {
    int p = lg[r - l + 1];
    return min(rmq[p][l].F, rmq[p][r - (1 << p) + 1].F);
}

int get_max(int l, int r) {
    int p = lg[r - l + 1];
    return max(rmq[p][l].S, rmq[p][r - (1 << p) + 1].S);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    for (int i = 1; i <= n; ++i) {
        rmq[0][i].F = 2 * a[i] - a[i + 1];
        rmq[0][i].S = 2 * a[i] - a[i - 1];
    }
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
            rmq[h][i].F = min(rmq[h - 1][i].F, rmq[h - 1][i + (1 << (h - 1))].F);
            rmq[h][i].S = max(rmq[h - 1][i].S, rmq[h - 1][i + (1 << (h - 1))].S);
        }
    }
    for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
    
    int q; cin >> q;
    for (int i = 1; i <= q; ++i) {
        int x; cin >> x;
        int low = 1, high = n, sol = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] <= x) {
                sol = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        int pos = 0;
        if (sol == 1) pos = sol;
        if (sol == n) pos = sol;
        if (sol != 1 && sol != n) pos = (abs(x - a[sol]) <= abs(x - a[sol + 1]) ? sol : sol + 1);
        
        ll ans = abs(x - a[pos]);
        int l = pos, r = pos;
        int steps = 0;
        while (l != 1 || r != n) {
            if (l == 1) {
                ans += a[n] - a[pos];
                break;
            }
            if (r == n) {
                ans += a[pos] - a[1];
                break;
            }
            ++steps;
            if (a[pos] - a[l - 1] <= a[r + 1] - a[pos]) {
                int low = 2, high = l - 1, sol = l;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (get_max(mid, l - 1) <= a[r + 1]) {
                        high = mid - 1;
                        sol = mid;
                    } else {
                        low = mid + 1;
                    }
                }
                ans += abs(a[pos] - a[sol - 1]);
                l = sol - 1;
                pos = sol - 1;
            } else {
                int low = r + 1, high = n - 1, sol = r;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (get_min(r + 1, mid) > a[l - 1]) {
                        low = mid + 1;
                        sol = mid;
                    } else {
                        high = mid - 1;
                    }
                }
                ans += abs(a[pos] - a[sol + 1]);
                r = sol + 1;
                pos = sol + 1;
            }
        }
        cout << ans << "\n";
    }
}

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