Submission #1241465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241465		mychecksedad	Overtaking (IOI23_overtaking)	C++17	100 / 100	1468 ms	121356 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long int
const int N = 2000;
const ll INF = LONG_LONG_MAX;

ll dp[N][N], L, X;
pair<ll, ll> pref[N][N];
int n, m;
vi W;
vector<ll> ST;
vector<ll> T;
set<array<ll, 3>> S;

void add(ll l, ll r, ll p){
  // cerr << "add: " << l  << ' ' << r << ' ' << p << '\n';
  if(S.empty()){
    S.insert(array<ll, 3>{l, r, p});
    return;
  }
  auto it = S.lower_bound(array<ll,3>{l, INF, -1});
  while(it != S.end() && (*it)[1] <= r){
    S.erase(it);
    it = S.lower_bound(array<ll,3>{l, INF, -1});
  }
  if(S.empty()){
    S.insert({l, r, p});
    return;
  }
  if(it == S.begin()){
    auto x = *it;
    if(x[0] > r){
      S.insert(array<ll, 3>{l, r, p});
    }else{
      S.erase(it);
      S.insert(array<ll, 3>{r + 1, x[1], x[2]});
      S.insert(array<ll, 3>{l, r, p});
    }
  }else{
    --it;
    auto x = *it;
    if(x[0] <= l && x[1] >= l){
      S.erase(it);
      if(x[0] < l){
        S.insert(array<ll, 3>{x[0], l - 1, x[2]});
      }
      if(x[1] > r){
        S.insert(array<ll, 3>{r + 1, x[1], x[2]}); // idk probably shouldnt exist
      }
    }
    if(S.empty()){
      S.insert(array<ll,3>{l, r, p});
      return;
    }
    it = S.lower_bound(array<ll,3>{l, INF, -1});
    if(it != S.end()){
      x = *it;
      if(x[0] > r){
        S.insert(array<ll, 3>{l, r, p});
      }else{
        S.erase(it);
        S.insert(array<ll, 3>{r + 1, x[1], x[2]});
        S.insert(array<ll, 3>{l, r, p});
      }
    }else{
      S.insert(array<ll,3>{l, r, p});
    }
  }
}

void init(int Lp, int nn, std::vector<long long> TT, std::vector<int> WW, int XX, int mm, std::vector<int> SS)
{
  ST.clear();
  L = Lp;
  X = XX;
  for(ll x: SS) ST.pb(x);
  W = WW;
  T = TT;
  n = nn;
  m = mm;
  W.pb(X);
  for(int i = 0; i < n; ++i) dp[0][i] = T[i];
  for(int i = 1; i < m; ++i){
    ll dif = ST[i] - ST[i - 1];
    vector<pair<ll, int>> q;
    for(int j = 0; j < n; ++j) q.pb({dp[i-1][j], j});
    sort(all(q));
    ll last = 0ll, last2 = 0ll;
    for(int j = 0; j < n; ++j){
      int p = q[j].ss;
      dp[i][p] = max(last, dp[i - 1][p] + dif * W[p]);
      last2 = max(last2, dp[i][p]);
      if(j + 1 < n && q[j+1].ff != q[j].ff) last=max(last,last2);
    }
    pref[i-1][0] = {q[0].ff, dp[i][q[0].ss]};
    for(int j = 1; j < n; ++j){
      pref[i-1][j].ff = q[j].ff;
      pref[i-1][j].ss = max(
        pref[i-1][j-1].ss,
        dp[i][q[j].ss]
      );
    }
  }

  for(int i = m-2; i >= 0; --i){
    vector<pair<ll, ll>> p;
    for(int j = 0; j < n; ++j){
      if(W[j] >= X){
        p.pb({dp[i][j] - ST[i] * X, dp[i + 1][j] - ST[i + 1] * X});
      }
    }
    sort(all(p));

    // cerr << i << '\n';
    // for(int j = 0; j < n; ++j){
    //   if(W[j] >= X)
    //   cerr << dp[i][j]  << ' ' << dp[i+1][j] << '\n';
    // }
    // cerr << '\n';
    // go lower to upper, update the set
    for(int j = 0; j < (int) p.size(); ++j){
      ll l = p[j].ff, r = p[j].ss, pt = p[j].ss;
      ++l; // due to overtaking 
      if(l > r) continue;
      // we'll try to map l...r to the point p is mapped into
      // where is p mapped into?
      auto it = S.lower_bound(array<ll, 3>{pt, INF, -1});
      if(it == S.begin() || S.size() == 0){
        // p is mapped into p...
        add(l, r, pt);
      }else{
        --it;
        if((*it)[1] >= pt)
          pt = (*it)[2];
        add(l, r, pt);
      }
    }
    // for(auto [l, r, p]: S) cerr << l << ' ' << r << ' ' << p << '\n';
    // cerr << '\n';
  }

  return;
}

long long arrival_time(long long Y)
{
  auto it = S.lower_bound(array<ll, 3>{Y, INF, -1});
  if(it == S.begin() || S.size() == 0){
    return Y + L * X;
  }
  --it;
  auto [l, r, p] = *it;
  if(r < Y) return Y + L * X;
  Y = p; // the mapped point
  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