Submission #845851

#	Time	Username	Problem	Language	Result	Execution time	Memory
845851		mircea_007	Overtaking (IOI23_overtaking)	C++17	100 / 100	1780 ms	471536 KiB

overtaking

#include "overtaking.h"

#pragma GCC optimize( "O3,Ofast,unroll-loops" ) // de ce nu

#include <stdio.h>
#include <stdlib.h>

#include <algorithm>
#include <vector>
#include <map>

using ll = long long;
#define magic_sauce inline __attribute__((always_inline))

magic_sauce ll max( ll a, ll b ){ return a > b ? a : b; }

const int MAXN = 1000;
const int MAXM = 1000;
const ll INF = 1e18;

const ll NIL = -1;

struct Range {
  ll begin;
  ll val;

  magic_sauce Range( ll a, ll b ) : begin( a ), val( b ) {}
};

struct Function {
  std::vector<Range> ranges;
  ll add;

  magic_sauce ll operator ()( ll x ){
    int st = 0, dr = (int)ranges.size(), mij;

    while( dr - st > 1 ){
      if( ranges[mij = (st + dr) >> 1].begin > x )
        dr = mij;
      else
        st = mij;
    }

    if( ranges[st].val >= 0 )
      return ranges[st].val;

    return x + add;
  }

  // compunerea de functii
  void operator *= ( Function &other ){
    std::vector<Range> new_ranges;
    int i, j, k, n = (int)ranges.size(), m = (int)other.ranges.size();;
    int st, dr, mij;

    ll start, end;

    for( i = 0 ; i < n ; i++ ){
      start = ranges[i].begin;

      if( i + 1 < n )
        end = ranges[i + 1].begin;
      else
        end = INF;
      
      if( ranges[i].val >= 0 )
        new_ranges.emplace_back( start, other( ranges[i].val ) );
      else{
        // functie liniara

        // [start, end) -> [start + add, end + add)

        // adaugam tot ce este in range-ul [it_start, it_end) doar ca + add
        // tratam separat intervalul ce contine pe start
        st = 0;
        dr = m;
        while( dr - st > 1 )
          if( other.ranges[mij = (st + dr) >> 1].begin > start + add )
            dr = mij;
          else
            st = mij;

        j = st;

        // cazul separat
        new_ranges.emplace_back( start, other.ranges[j].val );

        st = -1;
        dr = m;
        while( dr - st > 1 ){
          if( other.ranges[mij = (st + dr) >> 1].begin < end + add )
            st = mij;
          else
            dr = mij;
        }
        
        j++;
        k = dr;
        while( j < k ){
          new_ranges.emplace_back( other.ranges[j].begin - add, other.ranges[j].val );
          j++;
        }
      }
    }

    // prune next ranges
    ranges = new_ranges;

    add += other.add;
  }
};

struct Solver {
  int l, n, x, m;

  std::vector<ll> t0; // timpul de pornire al autobuzelor
  std::vector<int> speed; // s/m

  std::vector<int> stat; // sorting station

  ll dp[MAXM][MAXN];
  std::map<ll, ll> slowest[MAXM];

  Function f[MAXM];

  void calc_dp(){
    int i, j;

    // facem ce spune enuntul

    for( i = 0 ; i < n ; i++ )
      dp[0][i] = t0[i];

    for( i = 1 ; i < m ; i++ ){
      // for( j = 0 ; j < n ; j++ )
      //   e[j] = dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]);

      for( j = 0 ; j < n ; j++ )
        slowest[i][dp[i - 1][j]] = max( slowest[i][dp[i - 1][j]], dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]) );

      ll prev = -1;

      for( auto p : slowest[i] ){
        prev = max( slowest[i][p.first], prev );

        slowest[i][p.first] = prev;
      }

      for( j = 0 ; j < n ; j++ ){
        dp[i][j] = dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]);

        auto it = slowest[i].lower_bound( dp[i - 1][j] );
        if( it != slowest[i].begin() ){
          it--;

          dp[i][j] = max( dp[i][j], it->second );
        }
      }
    }
  }

  void calc_map( int i ){
    ll add = ((ll)x) * (stat[i] - stat[i - 1]);

    f[i].add = add;

    // daca am ajuns primii suntem liberi sa facem ce vrem
    f[i].ranges.emplace_back( 0, NIL );

    auto it = slowest[i].begin();
    auto next = it;

    while( it != slowest[i].end() ){
      next++;

      ll start = it->first;
      ll cand = it->second;

      ll end = INF;

      if( next != slowest[i].end() )
        end = next->first;

      start++;
      end++;

      // [start, cand - add) -> t' = cand
      // [cand - add, end) -> t' = t + add

      ll mij = cand - add;

      if( start < mij )
        f[i].ranges.emplace_back( start, cand );
      else
        mij = start;

      if( mij < end )
        f[i].ranges.emplace_back( mij, NIL );

      it = next;
    }
  }

  void compress_maps(){
    for( int p2 = 1 ; p2 < 1024 ; p2 <<= 1 )
      for( int i = 1 ; i + p2 < m ; i += (p2 << 1) )
        f[i] *= f[i + p2];
  }

  void pre(){
    // using the dp from the statement we precalculate the positions of the other bussesx
    calc_dp();

    // the old query function is a repeated aplication of M functions (in the math sense)
    // therefore we can hold these functions as a reunion of several intervals
    // each being either a constant function or a linear function with slope 1
    for( int i = 1 ; i < m ; i++ )
      calc_map( i );

    compress_maps();
  }

  ll query( ll t ){
    return f[1]( t );
  }

} sol;

void init( int L, int N, std::vector<ll> T, std::vector<int> W, int X, int M, std::vector<int> S ){
  // first of all, anything faster than x doesn't matter
  // therefore we can assume that the special bus in the
  // fastest one and the others are slowing it down

  // each buss has to worry only about the ones slower than itsself
  // for this exact reason, all the busse's paths (exept N) are predetermined

  // some precalculation

  sol.l = L;
  sol.n = N;
  sol.x = X;
  sol.m = M;

  sol.t0 = T;
  sol.speed = W;
  sol.stat = S;

  sol.pre();
}

ll arrival_time( ll Y ){
  return sol.query( Y );
  
  return 0;
}

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