Submission #911187

#	Time	Username	Problem	Language	Result	Execution time	Memory
911187		rxlfd314	Overtaking (IOI23_overtaking)	C++17	100 / 100	2319 ms	109400 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

static constexpr int mxN = 1000;
static map<arl2, ll> ans;
static int X, M;
static vt<int> S;
static vt<ll> T, times[mxN];

void init(int L, int N, vt<ll> _T, vt<int> W, int _X, int _M, vt<int> _S) {
  X = _X;
  S = _S;
  M = _M;
  T = _T;
  
  vt<arl2> cur;
  FOR(i, 0, N-1)
    cur.push_back({T[i], W[i]});
  
  FOR(i, 1, M-1) {
    sort(all(cur));
    vt<arl2> nxt;
    for (auto [t, s] : cur) {
      ll t2 = max(t + s * (S[i] - S[i-1]), size(times[i]) ? times[i].back() : 0ll);
      nxt.push_back({t2, s});
      times[i].push_back(t2);
      if (i == M-1)
        ans[{S[i], t2}] = t2;
    }
    cur = nxt;
  }
  
  ROF(i, M-2, 1)
    for (auto t : times[i]) {
      int ii = lower_bound(all(times[i]), t) - begin(times[i]) - 1;
      if (ii < 0)
        ans[{S[i], t}] = t + 1ll * X * (L - S[i]);
      else {
        int lo = i + 1, hi = M;
        while (lo < hi) {
          int mid = lo + hi >> 1;
          if (times[mid][ii] >= t + 1ll * X * (S[mid] - S[i]))
            hi = mid;
          else
            lo = mid + 1;
        }
        ans[{S[i], t}] = lo < M ? ans[{S[lo], times[lo][ii]}] : t + 1ll * X * (L - S[i]);
      }
      #ifdef DEBUG
      cout << "ans(" << S[i] << ", " << t << ") = " << ans[{S[i], t}] << '\n';
      #endif
    }
  
  sort(all(T));
} 

ll arrival_time(ll Y) {
  int i = lower_bound(all(T), Y) - begin(T) - 1;
  if (i < 0)
    return Y + 1ll * X * S[M-1];
  int lo = 1, hi = M;
  while (lo < hi) {
    int mid = lo + hi >> 1;
    if (times[mid][i] >= Y + 1ll * X * S[mid])
      hi = mid;
    else
      lo = mid + 1;
  }
  return lo < M ? ans[{S[lo], times[lo][i]}] : Y + 1ll * X * S[M-1];
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:53:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |           int mid = lo + hi >> 1;
      |                     ~~~^~~~
overtaking.cpp: In function 'll arrival_time(ll)':
overtaking.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = lo + hi >> 1;
      |               ~~~^~~~

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35