Submission #1015667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015667		onbert	Bitaro's travel (JOI23_travel)	C++17	100 / 100	1692 ms	288940 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int val, lpt, rpt;
};
const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e18;

vector<node> seg[maxN][2];
int def[2] = {INF, 0};
void build(int id, int l, int r, int i) {
    seg[id][i] = {{def[i], 0, 0}};
    if (l==r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid, i); build(id*2+1, mid+1, r, i);
}
void update(int id, int l, int r, int target, int i) {
    if (r<target || target<l) return;
    if (l==r) {
        seg[id][i].push_back({l, 0, 0});
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target, i); update(id*2+1, mid+1, r, target, i);
    if (i==0) {
        seg[id][i].push_back({min(seg[id*2][i].back().val, seg[id*2+1][i].back().val), (int)seg[id*2][i].size()-1, (int)seg[id*2+1][i].size()-1});
    } else {
        seg[id][i].push_back({max(seg[id*2][i].back().val, seg[id*2+1][i].back().val), (int)seg[id*2][i].size()-1, (int)seg[id*2+1][i].size()-1});
    }
}
int qry(int id, int pt, int l, int r, int findl, int findr, int i) {
    if (r<findl || findr<l) return def[i];
    // cout << l << " " << r << " " << pt << " " << seg[id][i][pt].val << endl;
    if (findl<=l && r<=findr) return seg[id][i][pt].val;
    int mid = (l+r)/2;
    int lhs = qry(id*2, seg[id][i][pt].lpt, l, mid, findl, findr, i);
    int rhs = qry(id*2+1, seg[id][i][pt].rpt, mid+1, r, findl, findr, i);
    if (i==0) return min(lhs, rhs);
    else return max(lhs, rhs);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int a[n+2];
    a[0] = -INF, a[n+1] = INF;
    for (int i=1;i<=n;i++) cin >> a[i];
    build(1, 1, n, 0); build(1, 1, n, 1);
    vector<pair<int,int>> R = {{-INF, -INF}};
    for (int i=1;i<=n;i++) R.push_back({2*a[i] - a[i+1], i});
    sort(R.begin()+1, R.end());
    for (int i=1;i<=n;i++) {
        update(1, 1, n, R[i].second, 0);
        // cout << R[i].second << " " << seg[1][0].back().val << endl;
    }

    vector<pair<int,int>> L = {{-INF, INF}};
    for (int i=1;i<=n;i++) L.push_back({-(2*a[i] - a[i-1]), i});
    sort(L.begin()+1, L.end());
    for (int i=1;i<=n;i++) update(1, 1, n, L[i].second, 1);

    // for (int i=1;i<=n;i++) {
    //     for (int j=1;j<=n;j++) cout << qry(1, i, 1, n, j, j, 1) << " "; cout << endl;
    // }
    // return 0;

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int pos = lower_bound(a+1, a+n+1, x) - a;
        if (x - a[pos-1] <= a[pos] - x) pos--;
        int ans = abs(x-a[pos]), l = pos, r = pos;
        bool state = 0;
        while (true) {
            if (l==1 || r==n) {
                ans += a[n] - a[1];
                break;
            }
            if (state==0) {
                int id = upper_bound(R.begin()+1, R.end(), make_pair(a[l-1], INF)) - R.begin() - 1;
                int nxt = qry(1, id, 1, n, r, n, 0);
                ans += a[nxt] - a[l];
                r = nxt;
            } else if (state==1) {
                int id = lower_bound(L.begin()+1, L.end(), make_pair(-a[r+1], -INF)) - L.begin() - 1;
                int nxt = qry(1, id, 1, n, 1, l, 1);
                ans += a[r] - a[nxt];
                l = nxt;
            }
            state = !state;
        }
        cout << ans << endl;
    }
}

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