Submission #1046761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046761		slivajan	Overtaking (IOI23_overtaking)	C++17	10 / 100	1 ms	600 KiB

overtaking

#include "overtaking.h"

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

typedef long long un;
typedef vector<un> vuc;
typedef tuple<un, un, un> tup;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un INF = INT64_MAX;

vec<vuc> prij;
vec<vuc> dalsi;
vec<vuc> goats;
vec<vec<tup>> seraz;
un speed;
vuc _S;
un _M;


void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    speed = X;

    _S = vuc(M);
    REP(i, 0, M) _S[i] = S[i];

    vuc _W(N);
    REP(i, 0, N) _W[i] = W[i];
    
    _M = M;

   prij = vec<vuc>(M, vuc(N, -1));
   dalsi = vec<vuc>(M, vuc(N, -1));
   goats = vec<vuc>(M, vuc(N, -1));
   prij[0] = T;

   REP(e, 0, M-1){
        vec<tup> toSort;
        REP(i, 0, N){
            toSort.push_back({prij[e][i], _W[i], i});
        }
        sort(ALL(toSort));

        seraz.push_back(toSort);

        un limit = 0;
        un nasl = -1;
        un lastOdj = -1;
        un lastIndex = -1;
        REP(i, 0, N){
            un odjezd, index;
            tie(odjezd, ignore, index) = toSort[i];
            if (lastOdj != odjezd) nasl = lastIndex;

            limit = max(limit, odjezd + _W[index] * (_S[e+1] - _S[e]));
            prij[e+1][index] = limit;
            dalsi[e][index] = nasl;

            lastOdj = odjezd;
            lastIndex = index;
        }

        un vor = -1;
        lastIndex = -1;
        for(un i = N-1; i > -1; i--){
            un odjezd, index;
            tie(odjezd, ignore, index) = toSort[i];
            if (lastOdj != odjezd) vor = index;

            goats[e][index] = vor;

            lastOdj = odjezd;
        }
   }

}

long long arrival_time(long long Y)
{
    un now = Y;
    tup what = {now, speed, -1};
    
    un snek;

    auto ptr = upper_bound(ALL(seraz[0]), what);
    if (ptr == seraz[0].begin()){
        return  now + speed * (_S[_M-1] - _S[0]);
    }
    else{
        ptr--;
        tie(ignore, ignore, snek) = *ptr;
    }


    REP(e, 0, _M-1){
        
        if (snek == -1){
            return now + speed * (_S[_M-1] - _S[e]);
        }

        if (now + speed * (_S[e+1] - _S[e]) <= prij[e+1][snek]){
            now = prij[e+1][snek];
            snek = dalsi[e+1][snek];
        }
        else{
            now = now + speed * (_S[e+1] - _S[e]);
            snek = goats[e+1][snek];
        }

        
    }

    return now;
}

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