Submission #1247663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247663		12baater	Overtaking (IOI23_overtaking)	C++20	39 / 100	3593 ms	24644 KiB

overtaking

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

using namespace std;
typedef long long ll;

const bool DEBUG = 0;


struct bus {
    int num;
    ll speed;
    ll time;
    bool operator<(const bus& other) const {
        if (time == other.time) return speed < other.speed;
        return time < other.time;
    }

    void print() {
        printf("Num: %d, speed %lld, time %lld\n", num, speed, time);
    }

};




struct ST {
    ll n;
    vector<ll> seg;
    ST (int N) : n(N), seg(2*N) {}

    void update(ll pos, ll val) {
        pos += n;
        while (pos > 0) {
            seg[pos] = max(seg[pos], val);
            pos >>= 1;
        }
    }

    ll query(ll time) {
        ll l = n;
        time += n;
        ll ret = 0;
        while (l < time) {
            if (l&1) ret = max(ret, seg[l++]);
            if (time&1) ret = max(ret, seg[--time]);
            time >>= 1;
            l >>= 1;
        }
        return ret;
    }
};


struct station {
    int num;
    ll dist;
    vector<bus> buses;

    void get_buses(station& other) {
        buses.clear();
        ll distDiff = dist-other.dist;
        sort(other.buses.begin(), other.buses.end());
        ll currentMax = 0;
        for (bus b : other.buses) {
            buses.push_back(b);
            currentMax = max(currentMax, b.time + (b.speed*distDiff));
            buses.back().time = currentMax;
        }
        if (DEBUG) {
            debug();
        }
    }

    void debug() {
        cout << "--------------\n";
        cout << num << ", dist: " << dist << "\n";
        for (bus b : buses) {
            b.print();
        }
        cout << "--------------\n";
    }

};

vector<bus> busesGlobal;
vector<station> stationGlobal;
bus specialBus;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    specialBus.speed = X;
    specialBus.num = N;
    for (int i = 0; i < N; i++) {
        bus b;
        b.num = i;
        b.speed = W[i];
        b.time = T[i];
        busesGlobal.push_back(b);
    }

    for (int i = 0; i < M; i++) {
        station stat;
        stat.dist = S[i];
        stat.num = i;
        stationGlobal.push_back(stat);
    }

    return;
}

long long arrival_time(long long Y)
{
    specialBus.time = Y;
    vector<bus> newVec;
    newVec.insert(newVec.end(), busesGlobal.begin(), busesGlobal.end());
    newVec.push_back(specialBus);
    sort(newVec.begin(), newVec.end());
    stationGlobal[0].buses = newVec;
    for (int i = 1; i < stationGlobal.size(); i++) {
        stationGlobal[i].get_buses(stationGlobal[i-1]);
    }

    for (bus b : stationGlobal.back().buses) {
        if (b.num == specialBus.num) return b.time;
    }
    return -1;
}

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