Submission #844327

#	Time	Username	Problem	Language	Result	Execution time	Memory
844327		LucaIlie	Overtaking (IOI23_overtaking)	C++17	9 / 100	3596 ms	23220 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;
const long long INF = 1e18;

struct bus {
    long long t;
    int v;
    int p;
};

struct answer {
    long long l, r, ans;
};

int n, m, x;
bus buses[MAX_N + 1], b[MAX_M][MAX_N + 1];
int s[MAX_M];
vector<answer> ans;
long long ymax, ymin;

long long query( long long y ) {
    for ( int j = 0; j < m - 1; j++ ) {
        int l = -1, r = n;
        while ( r - l > 1 ) {
            int mid = (l + r) / 2;
            if ( b[j][mid].t < y )
                l = mid;
            else
                r = mid;
        }
        y = y + (long long)x * (s[j + 1] - s[j]);
        if ( l >= 0 )
            y = max( y, b[j + 1][l].t );
    }

    return y;
}

void init( signed L, signed N, vector<long long> T, vector<signed> W, signed X, signed M, vector<signed> S ) {
    n = N;
    m = M;
    x = X;
    for ( int i = 0; i < n; i++ )
        buses[i] = { T[i], W[i], i };
    for ( int i = 0; i < m; i++ )
        s[i] = S[i];

    for ( int i = 0; i < n; i++ )
        b[0][i] = buses[i];
    ymax = 0;
    ymin = INF;
    for ( int i = 0; i < n; i++ ) {
        if ( b[0][i].v > x ) {
            ymax = max( ymax, b[0][i].t - (long long)x * s[0] );
            ymin = min( ymin, b[0][i].t - (long long)x * s[0] );
        }
    }
    for( int j = 0; j < m - 1; j++ ) {
        sort( b[j], b[j] + n, []( bus a, bus b ) {
            if ( a.t == b.t )
                return a.v < b.v;
            return a.t < b.t;
        } );

        for ( int i = 0; i < n; i++ )
            b[j + 1][i] = b[j][i];
        for ( int i = 0; i < n; i++ )
            b[j + 1][i].t = b[j][i].t + (long long)b[j][i].v * (s[j + 1] - s[j]);
        for ( int i = 1; i < n; i++ )
            b[j + 1][i].t = max( b[j + 1][i].t, b[j + 1][i - 1].t );
    }

    for ( int j = 0; j < m; j++ ) {
        for ( int i = 0; i < n; i++ ) {
            if ( b[j][i].v > x ) {
                ymax = max( ymax, b[j][i].t - (long long)x * s[j] );
                ymin = min( ymin, b[j][i].t - (long long)x * s[j] );
            }
        }
    }
    ymin = max( ymin, -1LL );

   // printf( "%lld %lld\n", ymin, ymax );
    long long y = ymin + 1;
    int cons = 0;
    while ( y < ymax ) {
        long long l = y, r = ymax;
        while ( r - l > 1 ) {
            long long mid = (l + r) / 2;

            if ( query( mid ) == query( y ) )
                l = mid;
            else
                r = mid;
        }

        //printf( "%lld %lld %lld\n", y, l, query( y ) );
        ans.push_back( { y, l, query( y ) } );
        if ( ans.size() > 1e5 )
            exit( 1 );
        y = r;
    }
    //printf( "%lld %lld\n", ymin, ymax );
}

long long arrival_time( long long y ) {
    if ( y >= ymax || y <= ymin )
        return y + (long long)x * s[m - 1];

    long long l = 0, r = ans.size();
    while ( r - l > 1 ) {
        long long mid = (l + r) / 2;

        if ( ans[mid].l <= y )
            l = mid;
        else
            r = mid;
    }

    return ans[l].ans;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:92:9: warning: unused variable 'cons' [-Wunused-variable]
   92 |     int cons = 0;
      |         ^~~~

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