Submission #1024863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024863		Svizel_pritula	Overtaking (IOI23_overtaking)	C++17	100 / 100	1590 ms	154196 KiB

overtaking

#include <bits/stdc++.h>

#include "overtaking.h"

typedef std::uint64_t u64;

struct bus
{
    u64 departure;
    u64 speed;
};

bool operator<(bus a, bus b)
{
    if (a.departure == b.departure)
        return a.speed < b.speed;

    return a.departure < b.departure;
}

struct segment
{
    u64 distance;
    std::map<u64, u64> lines;
    u64 offset = 0;

    u64 translate(u64 departure, u64 speed)
    {
        u64 arrival = departure + distance * speed;

        auto result = lines.lower_bound(departure + offset);

        if (result != lines.begin())
        {
            result--;
            arrival = std::max(arrival, result->second);
        }

        return arrival;
    }

    void layer(segment top, u64 speed)
    {
        std::vector<std::pair<u64, u64>> new_lines;

        for (auto l : top.lines)
        {
            u64 departure = l.first - top.offset;
            u64 arrival = l.second;

            arrival = translate(arrival, speed);

            new_lines.push_back({departure, arrival});
        }

        offset += top.distance * speed;
        distance += top.distance;

        for (auto l : new_lines)
        {
            u64 departure = l.first;
            u64 arrival = l.second;

            while (true)
            {
                auto result = lines.lower_bound(departure + offset);

                if (result == lines.end())
                    break;

                if (result->second >= arrival)
                    break;

                lines.erase(result);
            }

            lines.insert_or_assign(departure + offset, arrival);
        }
    }
};

segment simulate(std::vector<bus> &buses, u64 distance)
{
    segment s = segment{distance};
    u64 min_arrival = 0;

    for (auto &b : buses)
    {
        u64 arrival = b.departure + b.speed * distance;

        if (arrival > min_arrival)
            s.lines.insert_or_assign(b.departure, arrival);

        b.departure = std::max(min_arrival, arrival);
        min_arrival = b.departure;
    }

    std::sort(buses.begin(), buses.end());
    return s;
}

segment combined;
u64 speed;

void init(int road_length, int bus_count, std::vector<long long> departures, std::vector<int> speeds, int reserve_speed, int station_count, std::vector<int> stations)
{
    std::vector<bus> buses;

    for (size_t i = 0; i < bus_count; i++)
    {
        bus b = bus{(u64)departures[i], (u64)speeds[i]};

        if (b.speed > reserve_speed)
            buses.push_back(b);
    }

    std::sort(buses.begin(), buses.end());

    std::vector<segment> segments;

    for (size_t i = 1; i < station_count; i++)
    {
        u64 distance = stations[i] - stations[i - 1];
        segments.push_back(simulate(buses, distance));
    }

    combined = segments.back();

    for (auto s = segments.rbegin() + 1; s < segments.rend(); s++)
        combined.layer(*s, reserve_speed);

    speed = reserve_speed;
}

long long arrival_time(long long departure)
{
    return combined.translate(departure, speed);
}

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:109:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     for (size_t i = 0; i < bus_count; i++)
      |                        ~~^~~~~~~~~~~
overtaking.cpp:113:21: warning: comparison of integer expressions of different signedness: 'u64' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |         if (b.speed > reserve_speed)
      |             ~~~~~~~~^~~~~~~~~~~~~~~
overtaking.cpp:121:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |     for (size_t i = 1; i < station_count; i++)
      |                        ~~^~~~~~~~~~~~~~~

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