Submission #1000032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000032		abczz	Overtaking (IOI23_overtaking)	C++17	100 / 100	468 ms	67260 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long

using namespace std;

vector <array<ll, 2>> A;
vector <ll> U;
vector <vector <ll>> V;
vector <vector <array<ll, 2>>> nx;
ll z;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    A.clear();
    U.clear();
    V.resize(M);
    nx.resize(M);
    z = X;
    for (auto u : S) U.push_back(u);
    for (int i=0; i<N; ++i) {
        if (W[i] > X) {
            A.push_back({T[i], W[i]});
        }
    }
    if (A.empty()) return;
    ll p, l, r, mid;
    for (int i=0; i<M; ++i) {
        p = 0;
        sort(A.begin(), A.end(), [](auto a, auto b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
        });
        for (auto [x, y] : A) V[i].push_back(x);
        if (i == M-1) continue;
        for (auto &[x, y] : A) {
            x += (U[i+1]-U[i]) * y;
            p = x = max(p, x);
        }
    }
    nx[M-1].resize(V[0].size());
    for (int j=0; j<V[0].size(); ++j) nx[M-1][j] = {M-1, j};
    for (int i=M-2; i>=0; --i) {
        nx[i].resize(V[i].size());
        nx[i][0] = {i, 0};
        for (int j=1; j<V[i].size(); ++j) {
            l = i, r = M-1, mid;
            while (l < r) {
                mid = (l+r)/2;
                if (V[i][j]+(U[mid]-U[i]) * z <= V[mid][j-1]) r = mid;
                else l = mid+1;
            }
            if (V[i][j]+(U[l]-U[i]) * z <= V[l][j-1]) {
                nx[i][j] = nx[l][lower_bound(V[l].begin(), V[l].end(), V[l][j-1])-V[l].begin()];
            }
            else nx[i][j] = {i, j};
        }
    }
    return;
}

long long arrival_time(long long Y)
{
    if (V[0].empty()) return Y + U.back() * z;
    ll l, r, mid;
    l = 0, r = V[0].size()-1;
    while (l < r) {
        mid = (l+r+1)/2;
        if (V[0][mid] >= Y) r = mid-1;
        else l = mid;
    }
    if (V[0][l] >= Y) return Y + U.back() * z;
    ll a = l;
    l = 0, r = U.size()-1;
    while (l < r) {
        mid = (l+r)/2;
        if (Y+(U[mid] * z) <= V[mid][a]) r = mid;
        else l = mid+1;
    }
    if (Y+(U[l] * z) <= V[l][a]) {
        auto b = nx[l][a];
        return V[b[0]][b[1]] + (U.back()-U[b[0]]) * z;
    }
    else return Y + U.back() * z;
}

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:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int j=0; j<V[0].size(); ++j) nx[M-1][j] = {M-1, j};
      |                   ~^~~~~~~~~~~~
overtaking.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int j=1; j<V[i].size(); ++j) {
      |                       ~^~~~~~~~~~~~
overtaking.cpp:48:32: warning: right operand of comma operator has no effect [-Wunused-value]
   48 |             l = i, r = M-1, mid;
      |                                ^

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