제출 #1028247

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

travel

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

#define int ll

int n, q;
int a[N], x[N], y[N];

struct SparseTable {
    vector<int> lg;
    vector<int> mn[L];
    vector<int> mx[L];
    
    SparseTable(int n, int a[]) {
        lg.resize(n + 1);
        for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
        for (int i = 0; i < L; ++i) mn[i].resize(n + 1);
        for (int i = 0; i < L; ++i) mx[i].resize(n + 1);
        for (int i = 1; i <= n; ++i) mn[0][i] = a[i];
        for (int i = 1; i <= n; ++i) mx[0][i] = a[i];
        
        for (int h = 1; h < L; ++h) {
            for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
                mx[h][i] = max(mx[h - 1][i], mx[h - 1][i + (1 << (h - 1))]);
                mn[h][i] = min(mn[h - 1][i], mn[h - 1][i + (1 << (h - 1))]);
            }
        }
    } 
    
    int get_max(int l, int r) {
        int p = lg[r - l + 1];
        return max(mx[p][l], mx[p][r - (1 << p) + 1]);
    }
    int get_min(int l, int r) {
        int p = lg[r - l + 1];
        return min(mn[p][l], mn[p][r - (1 << p) + 1]);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) x[i] = 2 * a[i] - a[i + 1];
    for (int i = 1; i <= n; ++i) y[i] = 2 * a[i] - a[i - 1];
    SparseTable t1(n - 1, x), t2(n, y);
    
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int low = 1, high = n, pos = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] <= x) {
                low = mid + 1;
                pos = mid;
            } else {
                high = mid - 1;
            }
        }
        int l = pos, r = pos + 1;
        int cord = x;
        ll ans = 0;
        while (l != 0 || r != n + 1) {
            if (l == 0) {
                ans += a[n] - cord;
                r = n + 1;
                break;
            } 
            if (r == n + 1) {
                ans += cord - a[1];
                l = 0;
                break;
            }
            if (abs(cord - a[l]) <= abs(cord - a[r])) { // merge in stanga
                if (l == 1) {
                    ans += abs(cord - a[1]);
                    cord = a[1];
                    l = 0;
                    continue;
                }
                int low = 2, high = l, sol = l + 1;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    // 2 * a[mid] - a[mid - 1]
                    if (t2.get_max(mid, l) <= a[r]) {
                        high = mid - 1;
                        sol = mid;
                    } else {
                        low = mid + 1;
                    }
                }
                ans += abs(cord - a[sol - 1]);
                cord = a[sol - 1];
                l = sol - 2;
            } else { // merge in dreapta
                if (r == n) {
                    ans += abs(cord - a[n]);
                    cord = a[n];
                    r = n + 1;
                    continue;
                }
                int low = r, high = n - 1, sol = r - 1;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    // 2 * a[mid] - a[mid + 1]
                    if (t1.get_min(r, mid) > a[l]) {
                        low = mid + 1;
                        sol = mid;
                    } else {
                        high = mid - 1;
                    }
                }
                ans += abs(cord - a[sol + 1]);
                cord = a[sol + 1];
                r = sol + 2;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

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