Submission #998394

#	Time	Username	Problem	Language	Result	Execution time	Memory
998394		MilosMilutinovic	Overtaking (IOI23_overtaking)	C++17	100 / 100	1668 ms	161976 KiB

overtaking

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

using namespace std;

int n, m, x;
vector<int> w, s;
vector<vector<long long>> when;
set<array<long long, 3>> res;

void init(int l, int N, vector<long long> t, vector<int> W, int X, int M, vector<int> S) {
  n = N; m = M; x = X; w = W; s = S;
  when = vector<vector<long long>>(m, vector<long long>(n));
  when[0] = t;
  for (int i = 1; i < m; i++) {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
      if (when[i - 1][a] != when[i - 1][b]) {
        return when[i - 1][a] < when[i - 1][b];
      } else {
        return w[a] < w[b];
      }
    });
    long long mx = 0;
    for (int j = 0; j < n; j++) {
      int b = order[j];
      mx = max(mx, when[i - 1][b] + w[b] * 1LL * (s[i] - s[i - 1]));
      when[i][b] = mx;
    }
  }
  const long long inf = (long long) 1e18;
  set<array<long long, 3>> st;
  long long ft = 0;
  set<pair<long long, long long>> id;
  id.insert({inf, 0});
  auto Update = [&](long long L, long long R, long long val) {
    L = max(0LL, L);
    if (L > R) {
      return;
    }
    long long from = inf + 1, to = -1;
    while (true) {
      auto it = st.lower_bound({L, -1, -1});
      if (it == st.end() || (*it)[0] > R) {
        break;
      }
      long long l = (*it)[1], r = (*it)[2];
      st.erase(it);
      from = min(from, l);
      to = max(to, r);
    }
    {
      auto it = id.lower_bound({L, -1});
      if (it != id.end()) {
        long long pt = max(L, it->second);
        if (pt >= it->second && pt <= it->first) {
          from = min(from, pt);
        }
      }
    }
    {
      auto it = id.lower_bound({R, -1});
      if (it == id.end() || it->second > R) {
        if (it != id.begin()) {
          it = prev(it);
        }
      }
      if (it != id.end()) {
        long long pt = min(R, it->first);
        if (pt >= it->second && pt <= it->first) {
          to = max(to, pt);
        }
      }
    }
    if (from > to) {
      return;
    }
    while (true) {
      auto it = id.lower_bound({from, -1});
      if (it == id.end() || it->second > to) {
        break;
      }
      long long l = it->second, r = it->first;
      id.erase(it);
      if (l < from) {
        id.insert({from - 1, l});
      }
      if (r > to) {
        id.insert({r, to + 1});
      }
    }
    st.insert({val, from, to});
  };
  for (int i = 1; i < m; i++) {
    long long prv = ft;
    ft += (s[i] - s[i - 1]) * 1LL * x;
    vector<array<long long, 3>> ev;
    for (int j = 0; j < n; j++) {
      if (w[j] <= x) {
        continue;
      }
      long long L = when[i][j] - w[j] * 1LL * (s[i] - s[i - 1]) + 1, R = when[i][j] - x * 1LL * (s[i] - s[i - 1]);
      if (L > R) {
        continue;
      }
      ev.push_back({L, R + 1, when[i][j]});
    }
    vector<long long> xs;
    for (auto& p : ev) {
      xs.push_back(p[0]);
      xs.push_back(p[1]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int sz = (int) xs.size();
    vector<vector<long long>> qs(sz);
    for (auto& p : ev) {
      {
        int idx = (int) (lower_bound(xs.begin(), xs.end(), p[0]) - xs.begin());
        qs[idx].push_back(p[2]);
      }
      {
        int idx = (int) (lower_bound(xs.begin(), xs.end(), p[1]) - xs.begin());
        qs[idx].push_back(~p[2]);
      }
    }
    vector<array<long long, 3>> segs;
    {
      multiset<long long> st;
      for (int j = 0; j + 1 < sz; j++) {
        for (auto& v : qs[j]) {
          if (v >= 0) {
            st.insert(v);
          } else {
            st.erase(st.find(~v));
          }
        }
        if (!st.empty()) {
          segs.push_back({xs[j] - prv, xs[j + 1] - 1 - prv, *prev(st.end()) - ft});
        }
      }
    }
    reverse(segs.begin(), segs.end());
    for (auto& p : segs) {
      Update(p[0], p[1], p[2]);
    }
  }
  for (auto& p : st) {
    res.insert({p[2], p[1], p[0]});
  }
  return;
}

long long arrival_time(long long y) {
  auto it = res.lower_bound({y, -1, -1});
  if (it != res.end() && (*it)[1] <= y) {
    y = (*it)[2];
  }
  return y + s.back() * 1LL * x;
}

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