답안 #833071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
833071 2023-08-21T22:01:54 Z beaconmc Bitaro's travel (JOI23_travel) C++14
0 / 100
628 ms 3220 KB
#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 = upper_bound(pos.begin(), pos.end(), cur-rdis) - pos.begin() - 1;
        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";
    }


  }

}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 628 ms 3220 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -