Submission #1247824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247824		12baater	Overtaking (IOI23_overtaking)	C++20	39 / 100	3591 ms	89560 KiB

overtaking

#include "overtaking.h"
#include <set>
#include <map>
#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;
    ll distDiff;
    vector<bus> buses;
    vector<pair<ll, ll>> maxes;

    vector<pair<bool, ll>> maxIsBest;

    ll addToMap;

    void get_buses(station& other) {
        // buses.clear();
        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;
            maxes.emplace_back(b.time, currentMax);
            maxIsBest.emplace_back(0,0);
        }
        if (DEBUG) {
            debug();
        }
    }

    pair<ll, bool> get_arrival_time(bus& b) {
        addToMap = -1;
        if (maxes.empty()) {
            return {(b.speed*distDiff) + b.time, 0};
        }
        auto p = lower_bound(maxes.begin(), maxes.end(), make_pair(b.time, static_cast<ll>(0)));
        int place = distance(maxes.begin(), p);

        if (b.time > maxes.back().first) {
            if (maxes.back().second >= (b.speed*distDiff)+b.time) {
                addToMap = place;
            }
            return {max((b.speed*distDiff) + b.time, maxes.back().second), 0};
        }

        if (place == 0) {
            return {(distDiff*b.speed) + b.time, 0};
        }

        place--;
        if (maxIsBest[place].first) {
            return {maxIsBest[place].second, 1};
        }

        if (maxes[place].second >= (distDiff*b.speed)+b.time) {
            addToMap = place;
        }
        return {max((distDiff*b.speed)+b.time, maxes[place].second), 0};
    }

    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];

        if (b.speed <= X) continue;

        // bus specialbus;
        // specialbus.speed = X;
        // specialbus.time = T[i];
        // specialbus.num = N;
        busesGlobal.push_back(b);
        // busesGlobal.push_back(specialbus);
    }

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

    stationGlobal[0].buses = busesGlobal;
    for (int i = 1; i < M; i++) {
        stationGlobal[i].get_buses(stationGlobal[i-1]);
    }
    return;
}

long long arrival_time(long long Y)
{
    specialBus.time = Y;

    vector<station> a;

    bool b;
    for (int i = 1; i < stationGlobal.size(); i++) {
        pair<ll, bool> p = stationGlobal[i].get_arrival_time(specialBus);
        specialBus.time = p.first;
        b = p.second;
        if (b) {
            break;
        }
        
        if (stationGlobal[i].addToMap != -1) {
            a.push_back(stationGlobal[i]);
        }
    }

    // for (station b : a) {
    //     b.maxIsBest[b.addToMap] = {specialBus.time, 1};
    // }

    return specialBus.time;

    // 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