Submission #1132414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132414		mychecksedad	Bitaro's travel (JOI23_travel)	C++20	100 / 100	241 ms	33160 KiB

travel

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2e5+100, M = 1e5+10, K = 18, MX = 30;


int n, q, LOG2[N], dp[N][K], dp2[N][K];
ll a[N];
int get(int l, int r){
  int k = LOG2[r-l+1];
  return max(dp[l][k], dp[r-(1<<k)+1][k]);
}
int get2(int l, int r){
  int k = LOG2[r-l+1];
  return max(dp2[l][k], dp2[r-(1<<k)+1][k]);
}
void solve(){
  LOG2[1] = 0;
  for(int i = 2; i < N; ++i) LOG2[i] = LOG2[i/2] + 1;
  cin >> n;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    if(i>1) dp[i - 1][0] = 2*a[i] - a[i - 1];
    if(i>1) dp2[i - 1][0] = a[i] - 2*a[i - 1];
  }
  for(int j = 1; j < K; ++j){
    for(int i = 1; i + (1<<j) <= n; ++i){
      dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
      dp2[i][j] = max(dp2[i][j-1], dp2[i+(1<<(j-1))][j-1]);
    }
  }
  cin >> q;
  for(int i = 1; i <= q; ++i){
    ll s = 0; cin >> s;
    ll ans = 0;
    if(s >= a[n]){
      cout << s - a[1] << '\n';
      continue;
    }
    if(s <= a[1]){
      cout << a[n] - s << '\n';
      continue;
    }
    int pos = lower_bound(a+1, a+1+n, s) - a;
    int cur, l = 0, r = 0;
    if(s - a[pos - 1] <= a[pos] - s){
      l = pos - 1;
      r = pos - 1;
      ans += s - a[pos - 1];
    }else{
      l = pos, r = pos;
      ans += a[pos] - s;
    }
    cur = l;
    while(l != 1 || r != n){
      if(l == 1){
        ans += a[n] - a[cur]; 
        break;
      }
      if(r == n){
        ans += a[cur] - a[1]; 
        break;
      }
      bool go_left = 0;
      if(l == r){
        if(a[cur] - a[cur - 1] <= a[cur + 1] - a[cur]) go_left = 1;
      }else if(cur == r) go_left = 1;
      // cout << go_left << ' ';
      if(go_left){
        ll x = a[r + 1] - a[r] + a[r];
        int L = 1, R = l - 1, go = 1;
        while(L <= R){
          int m = L+R>>1;
          if(get(m, l-1) > x){
            go = m + 1;
            L = m + 1;
          }else{
            R = m - 1;
          }
        }
        ans += a[cur] - a[go];
        cur = go;
        l = go;
      }else{
        ll x = - a[l - 1];
        int L = r + 1, R = n, go = n;
        while(L <= R){
          int m = L+R>>1;
          if(get2(r, m-1) >= x){
            go = m - 1;
            R = m - 1;
          }else{
            L = m + 1;
          }
        }
        ans += a[go] - a[cur];
        cur = go;
        r = go;
      }
    } 
    cout << ans << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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