Submission #1210981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210981		hyakup	Overtaking (IOI23_overtaking)	C++20	65 / 100	3596 ms	63360 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll inf = 2e18;

ll tn;
ll l, n, m;

vector<int> stations;
struct Line{
  ll a, b, id; Line( ll a = 0, ll b = 0, ll id = 0 ) : a(a), b(b), id(id) {}
  bool operator < ( Line l ){
    if( b == l.b ) return a > l.a;
    return b > l.b;
  }

  ll calc( ll x ){ return a*x + b; }
};

vector<Line> bus;

vector<set<pair<ll, ll>>> s;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
  tn = X;
  l = L;
  n = N;
  m = M;

  s.resize(m);

  for( int i = 0; i < n; i++ ) bus.push_back(Line( W[i], T[i], i ));

  stations = S;

  vector<vector<int>> adj(n);
  vector<ll> t(n), marc(n);

  vector<Line> lines;
  for( auto x : bus ) lines.push_back(x);

  function<void(int, ll)> dfs = [&]( int cur, ll val ){
    t[cur] = val;
    marc[cur] = true;
    for( int viz : adj[cur] ) dfs( viz, val );
  };

  for( int pos = 1; pos < (int)stations.size(); pos++ ){
    fill( marc.begin(), marc.end(), 0);
    sort( lines.begin(), lines.end() );
    adj.clear();
    adj.resize(n);
    stack<pair<ll, int>> pilha;

    ll delta = stations[pos] - stations[pos - 1];
    for( auto x : lines ){
      t[x.id] = x.calc(delta);
      while( !pilha.empty() && pilha.top().first <= t[x.id] ){
        adj[x.id].push_back(pilha.top().second );
        pilha.pop();
      }

      pilha.push({ t[x.id], x.id });
    }

    reverse( lines.begin(), lines.end() );
    for( auto x : lines ){
      if( !marc[x.id] ) dfs( x.id, t[x.id] );
      s[pos - 1].insert({ x.b, t[x.id] });
    }
    s[pos - 1].insert({ -inf, -inf });

    lines.clear();
    for( auto x : bus ) lines.push_back(Line(x.a, t[x.id], x.id));
  }
}


ll arrival_time(ll y){

  for( int i = 0; i + 1 < (int)stations.size(); i++ ){
    auto [antes, depois] = *prev(s[i].lower_bound({ y, -inf }));
    ll delta = stations[i + 1] - stations[i];

    y = max( y + delta*tn, depois );
  }

  return y;
}

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