Submission #966605

#	Time	Username	Problem	Language	Result	Execution time	Memory
966605		abczz	Bitaro's travel (JOI23_travel)	C++14	15 / 100	433 ms	18516 KiB

travel

#include <iostream>
#include <array>
#define ll long long

using namespace std;

bool dir;
ll n, q, a, f, l, r, x, mid, A[200000], L[200000], R[200000];

struct SegTree{
  array <ll, 2> st[800000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = {L[l], R[l]};
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id][0] = max(st[id*2][0], st[id*2+1][0]);
    st[id][1] = min(st[id*2][1], st[id*2+1][1]);
  }
  ll queryL(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return -1e18;
    ll mid = (l+r)/2;
    if (ql <= l && r <= qr) {
      if (st[id][0] <= w) return -1e18;
      else if (l == r) return l;
      ll res = queryL(id*2+1, mid+1, r, ql, qr, w);
      if (res == -1e18) res = queryL(id*2, l, mid, ql, qr, w);
      return res;
    }
    ll res = queryL(id*2+1, mid+1, r, ql, qr, w);
    if (res == -1e18) res = queryL(id*2, l, mid, ql, qr, w);
    return res;
  }
  ll queryR(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return 1e18;
    ll mid = (l+r)/2;
    if (ql <= l && r <= qr) {
      if (st[id][1] >= w) return 1e18;
      else if (l == r) return l;
      ll res = queryR(id*2, l, mid, ql, qr, w);
      if (res == 1e18) res = queryR(id*2+1, mid+1, r, ql, qr, w);
      return res;
    }
    ll res = queryR(id*2, l, mid, ql, qr, w);
    if (res == 1e18) res = queryR(id*2+1, mid+1, r, ql, qr, w);
    return res;
  }
}ST;

int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i];
    R[i] = 1e18;
    L[i] = -1e18;
  }
  for (int i=1; i<n-1; ++i) {
    l = 0, r = i-1;
    while (l < r) {
      mid = (l+r)/2;
      if (A[i+1]-A[i] > A[i]-A[mid]) r = mid;
      else l = mid+1;
    }
    if (A[i+1]-A[i] > A[i]-A[l]) {
      R[i] = l;
    }
    l = i+1, r = n-1;
    while (l < r) {
      mid = (l+r+1)/2;
      if (A[i]-A[i-1] > A[mid]-A[i]) l = mid;
      else r = mid-1;
    }
    if (A[i]-A[i-1] > A[l]-A[i]) {
      L[i] = l;
    }
  }
  ST.build(1, 0, n-1);
  cin >> q;
  while (q--) {
    cin >> a;
    f = 0;
    auto it = lower_bound(A, A+n, a);
    if (it == A+n) {
      f += a - *prev(it);
      a = n-1;
    }
    else if (it == A) {
      f += *it-a;
      a = 0;
    }
    else if (a-*prev(it) <= *it-a) {
      f += a - *prev(it);
      a = it-A-1;
    }
    else {
      f += *it-a;
      a = it-A;
    }
    dir = 0;
    if (!a || (a != n-1 && A[a+1]-A[a] < A[a]-A[a-1])) dir = 1;
    l = r = a;
    //cout << l << " " << r << " " << f << '\n';
    while (l != 0 && r != n-1) {
      if (!dir) {
        x = ST.queryL(1, 0, n-1, 0, l-1, r);
        if (x == -1e18) {
          f += A[r]-A[0];
          l = 0;
        }
        else {
          f += A[r]-A[x];
          l = x;
        }
      }
      else {
        x = ST.queryR(1, 0, n-1, r+1, n-1, l);
        if (x == 1e18) {
          f += A[n-1]-A[l];
          r = n-1;
        }
        else {
          f += A[x]-A[l];
          r = x;
        }
      }
      //cout << l << " " << r << " " << f << '\n';
      dir ^= 1;
    }
    if (l != 0 || r != n-1) f += A[n-1]-A[0];
    cout << f << '\n';
  }
}

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