Submission #841494

#	Time	Username	Problem	Language	Result	Execution time	Memory
841494		model_code	Overtaking (IOI23_overtaking)	C++17	39 / 100	3567 ms	67464 KiB

overtaking

// time_limit/GA_cubic.cpp

// θ(N * M^2) in the worst case

#include "overtaking.h"
#include <algorithm>

using namespace std;
using ll = long long;

struct iv
{
    ll start;
    ll end;
    ll dest;
};

vector<iv> merge_intervals(const vector<iv> &iv1, const vector<iv> &iv2)
{
    vector<iv> result;
    int i = 0;
    for (int j = 0; j < iv2.size(); j++)
    {
        while (i < iv1.size() && iv1[i].dest <= iv2[j].start)
        {
            result.push_back(iv1[i]);
            i++;
        }
        ll start = iv2[j].start;
        if (i < iv1.size() && iv1[i].start <= start)
        {
            if (iv1[i].dest > iv2[j].end)
                continue;
            start = iv1[i].start;
        }
        while (i < iv1.size() && iv1[i].dest <= iv2[j].end)
        {
            i++;
        }
        ll end = iv2[j].end;
        if (i < iv1.size() && iv1[i].start <= end)
        {
            end = iv1[i].start;
        }
        result.push_back({start, end, iv2[j].dest});
    }
    while (i < iv1.size())
    {
        result.push_back(iv1[i]);
        i++;
    }
    return result;
}

vector<iv> intervals;
ll total_time;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    total_time = L * (ll)X;
    vector<pair<ll, int>> initial(N);
    for (int i = 0; i < N; i++)
    {
        initial[i] = {T[i], W[i]};
    }
    sort(initial.begin(), initial.end());
    vector<vector<ll>> bus_time(M, vector<ll>(N));
    vector<vector<int>> bus_rv(M, vector<int>(N));
    for (int j = 0; j < N; j++)
    {
        bus_time[0][j] = initial[j].first;
        bus_rv[0][j] = initial[j].second;
    }
    for (int i = 1; i < M; i++)
    {
        ll dist = S[i] - S[i - 1];
        ll m = 0;
        for (int j = 0; j < N; j++)
        {
            int rv = bus_rv[i - 1][j];
            ll t = bus_time[i - 1][j] + rv * dist;
            if (t <= m)
            {
                bus_time[i][j] = m;
                int k = j;
                while (k >= 1 && bus_time[i][k - 1] == m && bus_rv[i][k - 1] > rv)
                {
                    bus_rv[i][k] = bus_rv[i][k - 1];
                    k--;
                }
                bus_rv[i][k] = rv;
            }
            else
            {
                bus_time[i][j] = t;
                bus_rv[i][j] = rv;
                m = t;
            }
        }
    }
    for (int i = M - 1; i >= 1; i--)
    {
        ll dt = (S[i] - S[i - 1]) * (ll)X;
        for (iv &iv : intervals)
        {
            iv.start -= dt;
            iv.end -= dt;
            iv.dest -= dt;
        }
        vector<iv> intervals2;
        ll last_end = 0;
        for (int j = 0; j < N; j++)
        {
            if (bus_rv[i - 1][j] <= X)
                continue;
            if (bus_time[i][j] > last_end)
            {
                if (bus_time[i - 1][j] < last_end - dt)
                {
                    intervals2.back().end = bus_time[i - 1][j];
                }
                intervals2.push_back(
                    {bus_time[i - 1][j], bus_time[i][j] - dt, bus_time[i][j] - dt});
                last_end = bus_time[i][j];
            }
        }
        intervals = merge_intervals(intervals2, intervals);
    }
}

long long arrival_time(long long Y)
{
    int l = -1;
    int u = intervals.size();
    while (l + 1 < u)
    {
        int m = (l + u) / 2;
        if (intervals[m].start < Y && Y <= intervals[m].end)
        {
            return intervals[m].dest + total_time;
        }
        else if (Y <= intervals[m].start)
        {
            u = m;
        }
        else
        {
            l = m;
        }
    }
    return Y + total_time;
}

Compilation message (stderr)

overtaking.cpp: In function 'std::vector<iv> merge_intervals(const std::vector<iv>&, const std::vector<iv>&)':
overtaking.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int j = 0; j < iv2.size(); j++)
      |                     ~~^~~~~~~~~~~~
overtaking.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while (i < iv1.size() && iv1[i].dest <= iv2[j].start)
      |                ~~^~~~~~~~~~~~
overtaking.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         if (i < iv1.size() && iv1[i].start <= start)
      |             ~~^~~~~~~~~~~~
overtaking.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while (i < iv1.size() && iv1[i].dest <= iv2[j].end)
      |                ~~^~~~~~~~~~~~
overtaking.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if (i < iv1.size() && iv1[i].start <= end)
      |             ~~^~~~~~~~~~~~
overtaking.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<iv>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     while (i < iv1.size())
      |            ~~^~~~~~~~~~~~

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