Submission #727532

#	Time	Username	Problem	Language	Result	Execution time	Memory
727532		cig32	Bitaro's travel (JOI23_travel)	C++17	100 / 100	419 ms	20416 KiB

travel

#include "bits/stdc++.h"
#define int long long
using namespace std;
struct segtree_partial {
  vector<int> st;
  int stok;
  void u(int l, int r, int tar, int idx, int val) {
    if(l == r) {
      st[idx] = val;
      return;
    }
    int mid = (l+r) >> 1;
    if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
    else u(mid+1, r, tar, 2*idx+2, val);
    st[idx] = max(st[2*idx+1], st[2*idx+2]);
  }
  int qu1(int l, int r, int constl, int constr, int idx, int val) { // Last element in [l, r] > v
    if(l <= constl && constr <= r) {
      if(st[idx] <= val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        if(st[2*idx+2] > val) idx = 2*idx+2, constl = mid+1;
        else idx = 2*idx+1, constr = mid;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    if(mid < l || r < constl) return qu1(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1, val);
    else {
      int rchi = qu1(l, r, mid+1, constr, 2*idx+2, val);
      if(rchi != -1) return rchi;
      return qu1(l, r, constl, mid, 2*idx+1, val);
    }
  }
  int qu2(int l, int r, int constl, int constr, int idx, int val) { // First element in [l, r] > v
    if(l <= constl && constr <= r) {
      if(st[idx] <= val) return -1;
      while(constl < constr) {
        int mid = (constl + constr) >> 1;
        if(st[2*idx+1] > val) idx = 2*idx+1, constr = mid;
        else idx = 2*idx+2, constl = mid+1;
      }
      return constl;
    }
    int mid = (constl + constr) >> 1;
    if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr < l || r < mid+1) return qu2(l, r, constl, mid, 2*idx+1, val);
    else {
      int lchi = qu2(l, r, constl, mid, 2*idx+1, val);
      if(lchi != -1) return lchi;
      return qu2(l, r, mid+1, constr, 2*idx+2, val);
    }
  }
  void resize(int k) {
    stok = k;
    st.resize(4*k + 10);
  }
  void upd(int i, int v) { u(0, stok, i, 0, v); }
  int last_greater(int l, int r, int v) { return qu1(l, r, 0, stok, 0, v); }
  int first_greater(int l, int r, int v) { return qu2(l, r, 0, stok, 0, v); }
};
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int x[n+1];
  for(int i=1; i<=n; i++) cin >> x[i];
  segtree_partial y, z;
  y.resize(n);
  z.resize(n);
  for(int i=2; i<=n; i++) y.upd(i, 2*x[i]-x[i-1]);
  for(int i=1; i<n; i++) z.upd(i, x[i+1]-2*x[i]);
  int q;
  cin >> q;
  while(q--) {
    int s;
    cin >> s;
    int ll=1, rr=n;
    while(ll<rr) {
      int mid = (ll+rr+1)>>1;
      if(x[mid] <= s) ll=mid;
      else rr=mid-1;
    }
    int ans = 0;
    int cur; 
    int mn = 1e18;
    for(int i=max(1ll, ll-2); i<=min(n, ll+2); i++) {
      if(abs(x[i] - s) < mn) {
        mn = abs(x[i] - s);
        cur = i;
      }
    }
    ans += abs(x[cur] - s);
    int l=cur, r=cur;
    while(l!=1 || r!=n) {
      if(l == 1) {
        ans += x[n] - x[cur];
        break;
      }
      else if(r == n) {
        ans += x[cur] - x[1];
        break;
      }
      else if(l == cur) {
        int i = y.last_greater(2, l, x[r+1]);
        if(i != -1) {
          ans += x[cur] - x[i];
          ans += x[r+1] - x[i];
          r++;
          l = i;
          cur = r;
        }
        else {
          ans += x[cur] - x[1];
          ans += x[n] - x[1];
          break;
        }
      }
      else {
        int i = z.first_greater(r, n-1, -x[l-1] - 1);
        if(i != -1) {
          ans += x[i] - x[cur];
          ans += x[i] - x[l-1];
          l--;
          r = i;
          cur = l;
        }
        else {
          ans += x[n] - x[cur];
          ans += x[n] - x[1];
          break;
        }
      }
    }
    cout << ans << "\n";
  }
}

Compilation message (stderr)

travel.cpp: In function 'int32_t main()':
travel.cpp:102:12: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |       else if(r == n) {
      |            ^~

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