Submission #1018667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018667		NintsiChkhaidze	Bitaro's travel (JOI23_travel)	C++17	100 / 100	370 ms	13400 KiB

travel

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
using namespace std;

const int N = 2e5 + 5,mod = 1e9 + 7;
int a[N],t[5][4*N];

void build(int h,int l,int r){
  if (l == r){
    t[1][h] = 2*a[l] - a[l + 1];
    t[0][h] = 2*a[l] - a[l - 1];
    return;
  }

  build(left);
  build(right);
  t[1][h] = min(t[1][h*2],t[1][h*2+1]); 
  t[0][h] = max(t[0][h*2],t[0][h*2+1]); 
}

int getr(int h,int l,int r,int L,int R,int v){
  if (r < L || R < l) return -1;
  if (L <= l && r <= R) {
    if (t[1][h] > v) return -1;
    if (l == r) return l;
    if (t[1][h*2] <= v) return getr(left,L,R,v);
    return getr(right,L,R,v);
  }
  int y = getr(left,L,R,v);
  if (y != -1) return y;
  return getr(right,L,R,v);
}

int getl(int h,int l,int r,int L,int R,int v){
  if (r < L || R < l) return -1;
  if (L <= l && r <= R) {
    if (t[0][h] <= v) return -1;
    if (l == r) return l;
    if (t[0][h*2+1] > v) return getl(right,L,R,v);
    return getl(left,L,R,v);
  }
  int y = getl(right,L,R,v);
  if (y != -1) return y;
  return getl(left,L,R,v);
}

int main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

  int n;
  cin>>n;

  for (int i = 1; i <= n; i++){
    cin >> a[i];
  }

  build(1,1,n);

  int q;
  cin>>q;

  while (q--){

    int s;
    cin>>s;

    int le = 1,ri = n,R = n + 1;
    while (le <= ri){
      int mid = (le + ri) >> 1;
      if (a[mid] > s) {
        R = mid;
        ri = mid - 1;
      }else{
        le = mid + 1;
      }
    }

    le = 1; ri = n; int L = 0;
    while (le <= ri){
      int mid = (le + ri) >> 1;
      if (a[mid] < s){
        L = mid;
        le = mid + 1;
      }else{
        ri = mid - 1;
      }
    }

    int ans=0;
    if (L == 0){
      ans += (a[n] - s);
      cout<<ans<<endl;
      continue;
    }else if (R == n + 1){
      ans += (s - a[1]);
      cout<<ans<<endl;
      continue;
    }

    int dir = 1;
    //dir == 1 -> right
    //dir == 0 <- left

    if (a[R] - s < s - a[L]){
      dir = 1;
      ans += (a[R] - s);
      s = a[R];
    }else{
      dir = 0;
      ans += (s - a[L]);
      s = a[L];
    }

    while (L != 0 && R != n + 1){
      if (dir == 1){
        // vedzebt R -ze meti an tol umcires r-s romlistvisac
        //2*x[r] - x[r + 1] <= x[L]
        int r = getr(1,1,n,R,n,a[L]);
        if (r == -1) r = n;

        ans += a[r] - s;
        ans += a[r] - a[L];
        s = a[L];
        R = r + 1;
      }else{
        //vedzebt L-ze naklebi an tol udides l-s romlistvisac
        //2*x[l] - x[l - 1] > x[R] 

        int l = getl(1,1,n,1,L,a[R]);
        if (l == -1) l = 1;

        ans += s - a[l];
        ans += a[R] - a[l];
        s = a[R];
        L = l - 1;
      }

      dir ^= 1;
    }

    if (L == 0){
      ans += (a[n] - s);
    }else if (R == n + 1){
      ans += (s - a[1]);
    }

    cout<<ans<<endl;
  }
}

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