Submission #858871

#	Time	Username	Problem	Language	Result	Execution time	Memory
858871		superMOOZ	Overtaking (IOI23_overtaking)	C++17	19 / 100	87 ms	71660 KiB

overtaking

#include "overtaking.h"

#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

int L, N, X, M;
vector<long long> T;
vector<int> W, S;


pair<long long, int> arrival_vec[1005][1005];  // [stop][rank] = {time, id}
long long arrival_t[1005][1005];  // [stop][id]

vector<pair<long long, long long>> info[1005];  // sorted - [stop][..] = {from time, earliest arrival}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    ::L = L;
    ::N = N;
    ::T = T;
    ::W = W;
    ::X = X;
    ::M = M;
    ::S = S;
    for (int i=0; i<N; ++i) {
        arrival_vec[0][i] = {T[i], i};
        arrival_t[0][i] = T[i];
    }
    sort(arrival_vec[0], arrival_vec[0] + N);
    for (int stop=1; stop<M; ++stop) {
        long long earliest_arrival = 0;
        for (int i=0; i<N; ++i) {
            int id = arrival_vec[stop-1][i].second;
            long long arrival = arrival_t[stop-1][id] + 1LL*(S[stop]-S[stop-1])*W[id];
            arrival = max(arrival, earliest_arrival);
            arrival_vec[stop][i] = {arrival, id};
            arrival_t[stop][id] = arrival;
            earliest_arrival = arrival;
        }
        sort(arrival_vec[stop], arrival_vec[stop] + N);
    }
    // Preprocessing
    vector<pair<pair<long long, int>, long long>> tmap[1005];  // [stop] = {{{{time, state}, earliest arrival}}, ...}
    for (int stop=1; stop<M; ++stop) {
        for (auto p : arrival_vec[stop]) {
            long long arrival = p.first;
            int id = p.second;
            long long prev_from = p.first - 1LL*(S[stop]-S[stop-1])*W[id];
            long long prev_to = p.first - 1LL*(S[stop]-S[stop-1])*X;
            if (prev_from < prev_to) {
                tmap[stop-1].push_back({{prev_from + 1, 1}, arrival});
                tmap[stop-1].push_back({{prev_to, -1}, arrival});
            }
        }
    }
    for (int stop=0; stop<M-1; ++stop) {
        sort(tmap[stop].begin(), tmap[stop].end());
        priority_queue<long long> blockers;
        map<long long, int> mp;
        for (int i=0; i<tmap[stop].size(); ++i) {
            const auto& p = tmap[stop][i];
            long long time = p.first.first;
            int state = p.first.second;
            long long earliest_arrival = p.second;
            if (state == 1) {
                if (!mp[earliest_arrival]) blockers.push(earliest_arrival);
                mp[earliest_arrival]++;
            } else {
                mp[earliest_arrival]--;
            }
            if (i != tmap[stop].size()-1 && tmap[stop][i].first.first == tmap[stop][i+1].first.first) continue;
            while (!blockers.empty()) {
                long long x = blockers.top();
                if (mp[x] == 0) {
                    blockers.pop();
                    continue;
                }
                break;
            }
            if (blockers.empty()) {
                info[stop].push_back({time, 0});
            } else {
                info[stop].push_back({time, blockers.top()});
            }
        }
    }
    return;
}

long long arrival_time(long long Y)
{
    for (int stop=0; stop<M-1; ++stop) {
        int l=0, r=(int)info[stop].size() - 1;
        int res = -1;
        while (l<=r)  {
            int mid = (l+r)/2;
            if (info[stop][mid].first > Y) r = mid-1;
            else {
                res = mid;
                l = mid+1;
            }
        }
        long long earliest_arrival = 0;
        if (res != -1) earliest_arrival = info[stop][res].second;
        Y = max(earliest_arrival, Y + 1LL*(S[stop+1]-S[stop])*X);
    }
    return Y;
}

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:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i=0; i<tmap[stop].size(); ++i) {
      |                       ~^~~~~~~~~~~~~~~~~~
overtaking.cpp:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             if (i != tmap[stop].size()-1 && tmap[stop][i].first.first == tmap[stop][i+1].first.first) continue;
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~

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