Submission #1018661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018661		NintsiChkhaidze	Bitaro's travel (JOI23_travel)	C++17	15 / 100	3087 ms	3616 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 = 3e5 + 5,mod = 1e9 + 7;
int a[N];

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];
  }

  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 = n;
        for (int i = R; i < n; i++){
          if (2*a[i] - a[i + 1] <= a[L]) {r = i; break;}
        }

        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 = 1;
        for (int i = L; i > 1; i--){
          if (2*a[i] - a[i - 1] > a[R]) {l = i; break;}
        }

        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: 0 / 30
• Subtask 4: 0 / 55