Submission #1074719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074719		ProtonDecay314	Overtaking (IOI23_overtaking)	C++17	100 / 100	1534 ms	135216 KiB

overtaking

// AM + DG
#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

struct bus {
    ll v;
    ll s;
    ll e;
};

typedef vector<bus> vbu;

typedef vector<vbu> vvbu;


ll x;
vll s;
ll n;
ll m;

vbu cur_buses;
vvbu bus_configs;

/*
Idea:
arrival_time is a monotonically increasing function

subintervals of this function may be
assigned to a fixed value

This algorithm will compute this function

The representation I will use is a
set of [s, e, t], where s is the minimum
value of the interval (EXCLUSIVE),
e is the maximum value of the interval (INCLUSIVE),
and t is the value the interval maps to

In other words, f(x) = t if x is in (s, e]

To efficiently maintain this, I'll use the 
set data structure sorted by starting point
This allows me to efficiently find which intervals
are affected by a new interval that's about to be inserted

Operations to support:
1. Evaluate: find the containing interval, if any. Otherwise, map to identity
2. Insert and delete: insert a new interval; remove old ones that are fully contained
and edit affected intervals (there should only be two of these)

The data structure must also satisfy the "disjointness" invariant.
This is something I'll enforce myself

Maybe it's better to make an entire class for this to provide abstraction, haha
*/

struct Interval {
    // s = start
    // e = end
    // t = target value
    ll s, e, t;

    // The sorting within a set
    // Defines the bbst invariant
    bool operator<(const Interval& o) const {
        return s < o.s || (s == o.s && (e < o.e || (e == o.e && t < o.t))); 
    }

    void print() const {
        cout << "Interval { s = " << s << ", e = " << e << ", t = " << t << " }" << endl;
    }
};

typedef set<Interval> sint;
typedef vector<Interval> vint;

class IntFunc {
    public:
        sint ints;

        IntFunc() {};

        sint::iterator find_first_gte(ll n) {
            return ints.lower_bound({n, n, NINF(ll)});
        }

        ll evaluate(ll n) {
            auto it = find_first_gte(n);

            // (it)->print();
            // cout << "N = " << n << endl;
            // cout << "CT = " << ct << endl;

            if((it == ints.begin()) || ints.size() == 0ll) {
                return n; // No such element: return identity
            } else {
                // ! kinda a subtle bug, but it's possible ints.size() == 0,
                // in which case it-- is undefined
                it--;
                auto [cs, ce, ct] = *it;

                if(cs < n && n <= ce) {
                    return ct; // Fully contained in interval: return t
                } else return n;// Identity
            }

            // cout << "oops" << endl;
        }

        void insert(Interval i) {
            if(i.s >= i.e) return;

            // ! I SPENT HOURS DEBUGGING
            // ! BAHAHAHAH I WROTE INT INSTEAD OF LONG LONG
            // ! I'M SO SILLY AND QUIRKY Y'ALL
            // ! CHAT I'M ACTUALLY SILLY HAHAHAH
            // ! crazy!!
            ll new_val = evaluate(i.t); // new_val will be the new assigned value of the current interval

            // cout << "New val = " << new_val << endl;

            // print_state();

            // cout << "Inserting ... ";
            // i.print();

            if(ints.size() == 0ll) {
                // Insert automatically (we may run into segfault issues related to --ints.end() otherwise)
                ints.insert(i);
                return;
            }

            auto it_start_gte = find_first_gte(i.s); // It's possible it_start_gte - 1 is affected too (be careful)
            auto it_end_gte = find_first_gte(i.e); // it_end_gte is definitively not affected

            // Handle literal edge case(s)
            if(it_end_gte == ints.begin()) {
                ints.insert(i);
                return;
            }

            // Now, it_end_gte-- makes sense
            it_end_gte--;

            Interval old_prev_int, new_prev_int;
            bool prev_int_modified = false;

            if(it_start_gte != ints.begin()) {
                // it_start_gte - 1 exists. Check if it's affected
                old_prev_int = *prev(it_start_gte);

                // An interval (s1, e1] is affected by (s2, e2] when e2 > s1 and s2 < e1

                if(i.e > old_prev_int.s && old_prev_int.e > i.s) {
                    new_prev_int = {old_prev_int.s, i.s, old_prev_int.t};
                    prev_int_modified = true;
                }
            }

            // Check if it_end_gte is affected
            // Note that it may be possible that it_end_gte is completely
            // contained within the new interval. In this case, we
            // increment it_end_gte and remove it via the normal process
            Interval old_next_int, new_next_int;
            bool next_int_modified = false;

            old_next_int = *it_end_gte;

            // An interval (s1, e1] is contained within (s2, e2] when s2 <= s1 && e1 <= e2
            if(i.e > old_next_int.s && old_next_int.e > i.s && !(i.s <= old_next_int.s && old_next_int.e <= i.e)) {
                next_int_modified = true;
                new_next_int = {i.e, old_next_int.e, old_next_int.t};
            } else {
                // completely contained -- increment it_end_gte so that it's also erased
                it_end_gte++;
            }

            // Remove everything in (it_start_gte, it_end_gte)
            if(it_start_gte != ints.end() && it_start_gte != it_end_gte && prev(it_start_gte) != it_end_gte) {
                vint to_remove;

                // cout << "BONDMAN" << endl;
                // (it_start_gte)->print();
                // (it_end_gte)->print();
                // i.print();
                // ! Used to be prev(it_start_gte)
                for(auto it = it_start_gte; it != it_end_gte; it++) {
                    // Remove
                    to_remove.pb(*it);
                }

                for(Interval interval : to_remove) {
                    ints.erase(interval);
                }
            }

            if(prev_int_modified) {
                ints.erase(old_prev_int);
                if(new_prev_int.s < new_prev_int.e) ints.insert(new_prev_int);
            }

            if(next_int_modified) {
                // If this is the same as the previous int, it's okay
                // ints.erase is idempotent and will not error when you
                // erase something that's not there
                ints.erase(old_next_int);
                if(new_next_int.s < new_next_int.e) ints.insert(new_next_int);
            }

            // Finally finally finally, insert the new interval

            ints.insert({i.s, i.e, new_val});
        }

        void print_state() {
            cout << "IntFunc State:" << endl;

            for(Interval i: ints) {
                i.print();
            }

            cout << "IntFunc State End" << endl;
        }
};

IntFunc func_mapper;

void init(int L, int N, vll T, vi W, int X, int M, vi S)
{
    // ! No need to clear variables! This procedure is only called once :)) 

    L(i, 0ll, (ll)N) {
        if((ll)W[i] > (ll)X) {
            cur_buses.pb({(ll)(W[i]) - (ll)(X), T[i], T[i]});
        }
    }

    n = cur_buses.size();
    x = X;
    s.reserve(S.size());
    for(int sv : S) s.pb((ll)sv);
    m = M;

    L(i, 0ll, m) {
        vbu bus_configs_r;
        bus_configs.pb(bus_configs_r);
    }

    // Learning: vector assignment in C++
    // implicitly calls the copy constructor
    sort(cur_buses.begin(), cur_buses.end(), [](bus& b1, bus& b2) {return b1.e < b2.e || (b1.e == b2.e && b1.v < b2.v);});

    bus_configs[0] = cur_buses;

    typedef vector<pair<ll, Interval>> vpllint;

    vpllint bus_intervals_with_inds;

    L(i, 1ll, m) {
        // For each sorting station, simulate the advance of the buses

        sort(cur_buses.begin(), cur_buses.end(), [](bus& b1, bus& b2) {return b1.e < b2.e || (b1.e == b2.e && b1.v < b2.v);});
        L(j, 0ll, n) cur_buses[j].s = cur_buses[j].e;

        ll max_t = 0ll;

        ll ds = s[i] - s[i - 1ll];

        L(j, 0, n) {
            max_t = max(max_t, cur_buses[j].s + cur_buses[j].v * ds);
            cur_buses[j].e = max_t;
            bus_intervals_with_inds.pb({-i, {cur_buses[j].s, max_t, max_t}});
            // cout << "( " << cur_buses[j].s << ", " << cur_buses[j].e << " ), ";
        }
        // cout << "\n";

        bus_configs[i] = cur_buses;
    }

    sort(bus_intervals_with_inds.begin(), bus_intervals_with_inds.end());

    for(auto bus_with_depth_ind : bus_intervals_with_inds) {
        auto [_, interval] = bus_with_depth_ind;

        // cout << "Anya likes peanuts, Anya hates carrots" << endl;

        func_mapper.insert(interval);
    }

    // func_mapper.print_state();

    return;
}

ll arrival_time(ll Y)
{
    // cout << Y << " " << func_mapper.evaluate(Y) << endl;
    return func_mapper.evaluate(Y) + x * ((ll)(s[m - 1ll]) - (ll)(s[0ll]));
}

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