Submission #842063

#	Time	Username	Problem	Language	Result	Execution time	Memory
842063		Lucpp	Overtaking (IOI23_overtaking)	C++17	100 / 100	750 ms	233000 KiB

overtaking

#include <bits/stdc++.h>
#include "overtaking.h"
#define sz(x) (int)(size(x))
using namespace std;
using ll = long long;
constexpr ll inf = 2e18;

struct Segment{
    ll l, r, y1, y2;
    Segment(ll l_=0, ll r_=0, ll y1_=0, ll y2_=0):l(l_),r(r_),y1(y1_),y2(y2_){}
    ll eval(ll x)const{
        return y1 + (x-l)*((y2-y1)/(r-l));
    }
    Segment cut(ll cl, ll cr)const{
        ll nl = max(l, cl);
        ll nr = min(r, cr);
        ll ny1 = eval(nl);
        ll ny2 = eval(nr);
        return {nl, nr, ny1, ny2};
    };
    bool operator<(const Segment& o)const{
        if(l < o.l) return true;
        if(l > o.l) return false;
        return r < o.r;
    }
};
using Fun = vector<Segment>;
Fun merge(const Fun& f, const Fun& g){ // g(f(x))
    Fun res;
    int i = 0;
    for(Segment s : f){
        while(i < sz(g) && g[i].r <= s.y1) i++;
        if(s.y1 == s.y2){
            ll y = g[i].eval(s.y1);
            res.emplace_back(s.l, s.r, y, y);
        }
        else{
            while(i < sz(g)){
                Segment seg = g[i].cut(s.y1, s.y2);
                ll offset = s.l - s.y1;
                seg.l += offset, seg.r += offset;
                res.push_back(seg);
                if(seg.r < s.r) i++;
                else break;
            }
        }
    }
    return res;
}
vector<Fun> funs;
Fun myFun;

Fun dcMerge(int l, int r){
    if(l+1 == r) return funs[l];
    int m = (l+r)/2;
    Fun f = dcMerge(l, m);
    Fun g = dcMerge(m, r);
    return merge(f, g);
}

ll funEval(const Fun& f, ll x){
    auto it = --lower_bound(f.begin(), f.end(), Segment{x+1, x+1, 0, 0});
    return it->eval(x);
}

void dbg(const Fun& f){
    for(Segment s : f){
        cerr << s.l << " " << s.r << " " << s.y1 << " " << s.y2 << "\n";
    }
    cerr << "\n";
}

int L, M;
ll X;
vector<vector<pair<ll, ll>>> v;
vector<int> S;

void init(int Lin, int N, vector<ll> T, vector<int> W, int Xin, int Min, vector<int> Sin){
    L = Lin, M = Min, X = Xin, S = Sin;
    vector<int> ord(N);
    for(int i = 0; i < N; i++) ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int i, int j){return T[i] < T[j];});
    v.resize(M);
    for(int i : ord){
        if(W[i] <= X) continue;
        if(v[0].empty()) v[0].emplace_back(T[i], (ll)W[i]);
        else v[0].emplace_back(T[i], (ll)W[i]);
    }
    sort(v[0].begin(), v[0].end());
    for(int k = 1; k < M; k++){
        ll d = S[k]-S[k-1];
        ll lt1 = -1, lt2 = 0;
        Fun f;
        auto addSeg = [&](ll t){
            if(lt1 < t){
                ll spl = min(t+1, max(lt1+1, lt2 - X*d));
                if(spl > lt1+1) f.emplace_back(lt1+1, spl, lt2, lt2);
                if(spl <= t) f.emplace_back(spl, t+1, spl + X*d, t+1 + X*d);
            }
        };
        for(auto [t, w] : v[k-1]){
            ll e = t+w*d;
            ll t2 = max(lt2, e);
            v[k].emplace_back(t2, w);
            addSeg(t);
            lt1 = t, lt2 = t2;
        }
        sort(v[k].begin(), v[k].end());
        addSeg(inf);
        funs.push_back(f);
        // dbg(f);
    }
    myFun = dcMerge(0, M-1);
    // dbg(myFun);
}

ll arrival_time(ll Y){
    return funEval(myFun, Y);
    // ll t = Y;
    // for(int k = 0; k < M-1; k++){
    //     t = funEval(funs[k], t);
    // }
    // return t;
}

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