oj.uz

Submission #833065

# Submission time Handle Problem Language Result Execution time Memory
833065 2023-08-21T21:54:13 Z beaconmc Bitaro's travel (JOI23_travel) C++14
0 / 100
 1 ms 400 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 << n << "\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";
    }


  }

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 400 KB Output isn't correct
4 Halted 0 ms 0 KB -