Submission #1040858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040858		erray	Overtaking (IOI23_overtaking)	C++17	100 / 100	717 ms	123052 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/ioi23_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

constexpr int64_t max_Y = int64_t(1E18 + 5);

int L, X;
vector<array<int64_t, 2>> answers;
void init(int _L, int N, std::vector<long long> T, std::vector<int> W, int _X, int M, std::vector<int> S) {
  X = _X;
  L = _L;
  vector<pair<int64_t, int>> b;
  for (int i = 0; i < N; ++i) {
    if (W[i] > X) {
      b.emplace_back(T[i], W[i] - X);
    }
  }
  N = int(b.size());
  sort(b.begin(), b.end());
  set<array<int64_t, 4>> mapping;
  {
    int64_t last = -1;
    for (int i = 0; i <= N; ++i) {
      int64_t r = (i == N ? max_Y : b[i].first);
      if (last != r) {
        int64_t l = last +1;
        mapping.insert({l, r, l, r});
        last = r;
      }
    }
  }
  for (int t = 1; t < M; ++t) {
    int len = S[t] - S[t - 1];
    sort(b.begin(), b.end());
    for (int i = 0; i < N; ++i) {
      b[i].first += 1LL * b[i].second * len;
    }
    int64_t mx = -1;
    for (int i = 0; i < N; ++i) {
      mx = max(mx, b[i].first);
      b[i].first = mx;
    }
    sort(b.begin(), b.end());
    int64_t mn = int64_t(4E18);
    for (int i = N - 1; i >= 0; --i) {
      int64_t to = b[i].first;
      int64_t from = to - 1LL * b[i].second * len;
      if (from >= mn) {
        continue;
      }
      mn = from;
      auto it = mapping.lower_bound(array<int64_t, 4>{from + 1, -1, -1, -1});
      array<int64_t, 2> range{-1, -1};
      while (it != mapping.end() && (*it)[0] <= to) {
        if ((*it)[1] <= to) {
          if (range[0] == -1) range[0] = (*it)[2];
          range[1] = (*it)[3];
          it = mapping.erase(it); 
        } else {
          auto cur = *it;
          mapping.erase(it);
          if (range[0] == -1) range[0] = cur[2];
          range[1] = to;
          assert(cur[1] == cur[3]);
          mapping.insert({to + 1, cur[1], to + 1, cur[3]});
          break;
        }
      }
      if (range[0] != -1) {
        mapping.insert({to, to, range[0], range[1]}); 
      }
    } 
  }
  for (auto[ll, rr, l, r] : mapping) {
    if (ll == rr) answers.push_back({r, ll});
    else answers.push_back({r, -1});
  }
}

long long arrival_time(long long Y) {
  int64_t ans = (*lower_bound(answers.begin(), answers.end(), array<int64_t, 2>{Y, -1}))[1];
  int64_t lost = 1LL * X * L;
  return (ans == -1 ? lost + Y : ans + lost);
}

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