Submission #1293224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293224		lto5	Bitaro's travel (JOI23_travel)	C++20	100 / 100	267 ms	4960 KiB

travel

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
#define left left_
#define right right_

int n;
int a[N];
int q;
int64_t best[N];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
#define task "a"
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
  }
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  a[n + 1] = 2e9;
  cin >> q;
  for (int i = 1; i <= n; i++) {
    int L = i, R = i;
    int pos = i;
    int64_t& ans = best[i];
//    ans += a[i];
    while (L > 1 || R < n) {
//      if (i == 4) cerr << i << " " << L << " " << R << endl;
      if (L == 1) {
        ans += abs(a[n] - a[pos]);
        break;
      }
      if (R == n) {
        ans += abs(a[1] - a[pos]);
        break;
      }
      /// go right
      if (abs(a[pos] - a[R + 1]) < abs(a[pos] - a[L - 1])) {
//        cerr << "R";
        int right = a[pos] + abs(a[pos] - a[L - 1]);
        int next_pos = lower_bound(a + 1, a + n + 1, right) - a - 1;
        ans += abs(a[next_pos] - a[pos]);
        pos = next_pos;
        R = next_pos;
      }
      else { /// left
        int left = a[pos] - abs(a[pos] - a[R + 1]);
//        cerr << "L " << left << " ";
        int left_pos = lower_bound(a + 1, a + n + 1, left) - a;
//        cerr << left_pos << endl;
        ans += abs(a[left_pos] - a[pos]);
        L = left_pos;
        pos = left_pos;
      }
    }
  }
  while (q--) {
    int x;
    cin >> x;
    int u = 1;
    int j = upper_bound(a + 1, a + n + 1, x) - a;
    for (int i = max(j - 1, 1); i <= min(j + 1, n); i++) {
      if (abs(x - a[u]) > abs(x - a[i])) u = i;
    }
    cout << abs(x - a[u]) + best[u] << "\n";
  }
  return 0;
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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