Submission #833072

#	Time	Username	Problem	Language	Result	Execution time	Memory
833072		beaconmc	Bitaro's travel (JOI23_travel)	C++14	100 / 100	733 ms	7928 KiB

travel

#include <bits/stdc++.h>


typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


int main(){
  ll n;
  cin >> n;
  vector<ll> pos(n);
  FOR(i,0,n) cin >> pos[i];

  ll q;
  cin >> q;

  FOR(i,0,q){
    ll cur;
    cin >> cur;

    ll left = upper_bound(pos.begin(), pos.end(), cur) - pos.begin() - 1;
    ll right = upper_bound(pos.begin(), pos.end(), cur) - pos.begin();

    if (left < 0){
      cout << abs(cur-pos[n-1]) << "\n";
      continue;
    }
    if (right > n-1){
      cout << abs(cur-pos[0]) << "\n";
      continue;
    }
    ll ans = 0;

    while (left>=0 && right<=n-1){
    
      ll ldis = abs(cur-pos[left]);
      ll rdis = abs(cur - pos[right]);
      if (ldis > rdis){
        ll maxpos = upper_bound(pos.begin(), pos.end(), cur+ldis-1) - pos.begin() - 1;
        if (maxpos > n-1) maxpos = n-1;
        ans += abs(pos[maxpos]-cur);
        cur = pos[maxpos];
        right = maxpos+1;
        
      }else{
        ll maxpos = lower_bound(pos.begin(), pos.end(), cur-rdis) - pos.begin();
        if (maxpos < 0) maxpos = 0;
        ans += abs(pos[maxpos]-cur);
        cur = pos[maxpos];
        left = maxpos-1;

      }
    }



    if (left<0){
      cout << ans + abs(cur-pos[n-1]) << "\n";
    }else{
      cout << ans + abs(cur-pos[0]) << "\n";
    }


  }

}

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