Submission #1046399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046399		Trustfulcomic	Overtaking (IOI23_overtaking)	C++17	65 / 100	3561 ms	33372 KiB

overtaking

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

typedef long long ll;
using namespace std;

struct bus{
    ll t;
    ll exp_nt;
    ll real_nt;
    ll v;
};

vector<vector<bus>> buses;
ll M_glob;
vector<int> s;
ll x;

void sort_bus(int i){
    sort(buses[i].begin(), buses[i].end(), [](bus& a, bus& b){
        return (a.t < b.t || (a.t == b.t && a.exp_nt < b.exp_nt));
    });
}

void calc_real_nts(int i){
    sort_bus(i);
    ll last_max = -1;
    ll current_max = -1;
    for (int j = 0; j<buses[i].size(); j++){
        if (j != 0 && buses[i][j].t != buses[i][j-1].t){
            last_max = current_max;
        }
        current_max = max(buses[i][j].exp_nt, current_max);
        buses[i][j].real_nt = max(last_max, buses[i][j].exp_nt);
    }
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    buses = vector<vector<bus>>(M-1, vector<bus>(N));
    M_glob = M;
    s = S;
    x = X;

    for (int i = 0; i<N; i++){
        buses[0][i].t = T[i];
        buses[0][i].v = W[i];
        buses[0][i].exp_nt = T[i]+((ll)S[1])*W[i];
    }
    
    for (int i = 0; i<M-1; i++){
        calc_real_nts(i);
        if (i != M-2){
            for (int j = 0; j<N; j++){
                buses[i+1][j] = {buses[i][j].real_nt, buses[i][j].real_nt+(S[i+2]-S[i+1])*buses[i][j].v, -1, buses[i][j].v};
            }
        }
    }

    return;
}

int bin_s(ll t, int m){
    int l = 0;
    int r = buses[m].size()-1;
    while (l<r){
        int mid = (l+r+1)/2;
        if (buses[m][mid].t >= t){
            r = mid-1;
        } else {
            l = mid;
        }
    }
    if (buses[m][l].t >= t){
        return l-1;
    } else {
        return l;
    }
}

long long arrival_time(long long Y)
{
    ll cur_t = Y;

    for (int i = 0; i<M_glob-1;i++){
        int j = bin_s(cur_t, i);

        ll my_exp_nt = cur_t+(s[i+1]-s[i])*x;
        if (j >= 0) cur_t = max(my_exp_nt, buses[i][j].real_nt);
        else cur_t = my_exp_nt;
    }

    return cur_t;
}

Compilation message (stderr)

overtaking.cpp: In function 'void calc_real_nts(int)':
overtaking.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bus>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int j = 0; j<buses[i].size(); j++){
      |                     ~^~~~~~~~~~~~~~~~

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