Submission #1070846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070846		Soumya1	Overtaking (IOI23_overtaking)	C++17	100 / 100	984 ms	138932 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mxY = 1e18;
ll X;
vector<pair<ll, ll>> ans;
vector<ll> v;
ll L;
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<ll, ll>> all;
  for (int i = 0; i < n; i++) {
    if (W[i] <= X) continue;
    all.push_back({T[i], W[i] - X});
  }
  n = all.size();
  sort(all.begin(), all.end());
  set<array<ll, 4>> st;
  if (n) st.insert({0, all[0].first, 0, all[0].first});
  for (int i = 0; i < n; i++) {
    if (i + 1 == n) {
      st.insert({all[i].first + 1, mxY, all[i].first + 1, mxY});
    } else {
      if (all[i].first == all[i + 1].first) continue;
      st.insert({all[i].first + 1, all[i + 1].first, all[i].first + 1, all[i + 1].first});
    }
  }
  for (int j = 1; j < m; j++) {
    for (int i = 0; i < n; i++) {
      all[i].first += 1LL * (S[j] - S[j - 1]) * all[i].second;
      if (i > 0) all[i].first = max(all[i].first, all[i - 1].first);
    }
    sort(all.begin(), all.end());
    ll done = 2e18;
    for (int i = n - 1; i >= 0; i--) {
      ll point = all[i].first - 1LL * (S[j] - S[j - 1]) * all[i].second;
      if (done <= point) continue;
      done = point;
      ll mn = 2e18, mx = -2e18;
      while (true) {
        auto it = st.upper_bound({point + 1, -1, -1, -1});
        if (it == st.end()) break;
        if ((*it)[0] > all[i].first) break;
        if ((*it)[1] <= all[i].first) {
          mn = min(mn, (*it)[2]);
          mx = max(mx, (*it)[3]);
          st.erase(it);
        } else {
          mn = min(mn, (*it)[2]);
          mx = max(mx, all[i].first);
          auto cur = *it;
          st.erase(it);
          st.insert({all[i].first + 1, cur[1], all[i].first + 1, cur[1]});
        }
      }
      if (mn != 2e18) {
        st.insert({all[i].first, all[i].first, mn, mx});
      }
    }
  }
  for (auto x : st) {
    if (x[0] == x[1]) ans.push_back({x[2], x[3]}), v.push_back(x[0]);
  }
}
long long arrival_time(long long Y) {
  auto it = upper_bound(ans.begin(), ans.end(), pair<ll, ll> {Y, 2e18}) - ans.begin() - 1;
  if (it < 0 || it >= ans.size()) return Y + L * X;
  if (ans[it].first <= Y && Y <= ans[it].second) return v[it] + L * X;
  return Y + L * X;
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:68:20: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if (it < 0 || it >= ans.size()) return Y + L * 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