제출 #1165480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165480		antonn	Bitaro's travel (JOI23_travel)	C++20	0 / 100	3095 ms	528 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;

int a[N];

int get_min(int l, int r) {
    int ans = 2e9;
    for (int i = l; i <= r; ++i) ckmin(ans, 2 * a[i] - a[i + 1]);
    return ans;
}

int get_max(int l, int r) {
    int ans = -2e9;
    for (int i = l; i <= r; ++i) ckmax(ans, 2 * a[i] - a[i - 1]);
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    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;
        while (l != 1 || r != n) {
            if (l == 1) {
                ans += a[n] - a[pos];
                break;
            }
            if (r == n) {
                ans += a[pos] - a[1];
                break;
            }
            if (a[pos] - a[l - 1] <= a[r + 1] - a[pos]) {
                int low = 2, high = l, sol = 0;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (get_max(mid, l) <= 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, high = n - 1, sol = 0;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (get_min(r, 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