Submission #1243536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243536		Hamed_Ghaffari	Overtaking (IOI23_overtaking)	C++20	9 / 100	1 ms	1604 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define mid ((l+r)>>1)

const int MXN = 1003;
const ll MX = 1'000'000'001'000'000'003;

inline pll eval(pll f, ll x) { return pll(x+f.ff, f.ss); }
inline bool cmp(pll f, pll g) {
    return (__int128_t)f.ff*g.ss <= (__int128_t)g.ff*f.ss;
}
inline pair<pll, int> min_(pair<pll, int> x, pair<pll, int> y) {
    return cmp(x.ff, y.ff) ? x : y;
}

struct lichao {
    lichao *lc, *rc;
    pll f;
    int id;
    lichao(): lc(NULL), rc(NULL), f(pll(MX, 1)), id(-1) {}
    lichao *cpy() {
        lichao *v = new lichao();
        v->lc = lc, v->rc = rc, v->f = f;
        return v;
    }
    void del() {
        if(lc) lc->del();
        if(rc) rc->del();
        delete this;
    }
};

lichao *add(pll f, int id, lichao *vv, bool pers, ll l=0, ll r=MX) {
    if(!vv) {
        lichao *v = new lichao();
        v->f = f;
        v->id = id;
        return v;
    }
    lichao *v = pers ? vv->cpy() : vv;
    if(r-l == 1) {
        if(cmp(eval(f, l), eval(v->f, l))) {
            v->f = f;
            v->id = id;
        }
        return v;
    }
    bool L = cmp(eval(f, l), eval(v->f, l));
    bool M = cmp(eval(f, mid), eval(v->f, mid));
    if(M) {
        swap(f, v->f);
        swap(id, v->id);
    }
    if(L==M) v->rc = add(f, id, v->rc, pers, mid, r);
    else v->lc = add(f, id, v->lc, pers, l, mid);
    return v;
}

pair<pll, int> get(ll x, lichao *v, ll l=0, ll r=MX) {
    if(!v) return {{MX, 1}, -1};
    return min_({eval(v->f, x), v->id}, x<mid ? get(x, v->lc, l, mid) : get(x, v->rc, mid, r));
}


int L, n, m, X, ord[MXN];
vector<ll> T;
vector<int> W, S;
ll t[MXN][MXN], e[MXN][MXN], dp[MXN][MXN];
lichao *root[MXN];

void init(int L_, int N, vector<ll> T_, vector<int> W_, int X_, int M, vector<int> S_) {
    L = L_, n = N, T = T_, W = W_, X = X_, m = M, S = S_;
    int ptr=0;
    for(int i=0; i<n; i++)
        if(W[i]>X) {
            T[ptr] = T[i];
            W[ptr++] = W[i];
        }
    n = ptr;
    if(n==0) return;
    for(int i=0; i<n; i++)
        t[i][0] = T[i];
    iota(ord, ord+n, 0);
    for(int j=0; j+1<m; j++) {
        sort(ord, ord+n, [&](int x, int y) {
            return t[x][j] < t[y][j];
        });
        for(int i=0; i<n; i++)
            e[i][j+1] = t[i][j] + 1ll*W[i]*(S[j+1]-S[j]);
        ll mx = 0;
        for(int l=0,r; l<n; ) {
            r=l;
            while(r+1<n && t[ord[r+1]][j]==t[ord[r]][j]) r++;
            ll mx2=mx;
            for(int i=l; i<=r; i++)
                mx2 = max(mx2, e[ord[i]][j+1]),
                t[ord[i]][j+1] = max(e[ord[i]][j+1], mx);    
            mx = mx2;
            l=r+1;
        }
    }
    // for(int i=0; i<n; i++) {
    //     cout << t[i][0] << ' ';
    //     for(int j=1; j<m; j++) {
    //         cout << e[i][j] << ' ' << t[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';

    for(int j=m-2; j>=0; j--) {
        sort(ord, ord+n, [&](int x, int y) {
            return t[x][j] < t[y][j];
        });
        lichao *ds = NULL;
        for(int i=0; i<n; i++) {
            if(t[ord[i]][j]>t[ord[0]][j]) {
                auto x = get(t[ord[i]][j], ds);
                // cout << ord[i] << ' ' << j << ": " << t[ord[i]][j] << ' ' << x.ff.ff << ' ' << x.ff.ss << ' ' << x.ss << '\n';
                ll up = x.ff.ff, dw = x.ff.ss;
                int pos = lower_bound(S.begin(), S.end(),
                    S[j]+(up+dw-1)/dw)-S.begin();
                if(pos==m)
                    dp[ord[i]][j] = 1ll*X*(L-S[j]);
                else
                    dp[ord[i]][j] = t[x.ss][pos]-t[ord[i]][j]
                        + dp[x.ss][pos];
            }
            else
                dp[ord[i]][j] = 1ll*X*(L-S[j]);
            ds = add({-t[ord[i]][j], W[ord[i]]-X}, ord[i], ds, 0);
        }
        ds->del();
    }
    sort(ord, ord+n, [&](int i, int j) {
        return t[i][0] < t[j][0];
    });
    lichao *ds = NULL;
    for(int i=0; i<n; i++)
        root[i] = ds = add({-t[ord[i]][0], W[ord[i]]-X}, ord[i], ds, 1);
    // for(int i=0; i<n; i++) cout << T[i] << ' ' << W[i] << '\n';
    // for(int i=0; i<n; i++) {
    //     for(int j=0; j<m; j++)
    //         cout << dp[i][j] << ' ';
    //     cout << '\n';
    // }
}

ll arrival_time(ll Y) {
    if(n==0 || t[ord[0]][0]>=Y) return Y + 1ll*X*L;
    int l=0, r=n;
    while(r-l>1)
        (t[ord[mid]][0]<Y ? l : r) = mid;
    auto x = get(Y, root[l]);
    ll up = x.ff.ff, dw = x.ff.ss;
    int pos = lower_bound(S.begin(), S.end(),
        (up+dw-1)/dw)-S.begin();
    if(pos==m) return Y + 1ll*X*L;
    return t[x.ss][pos] + dp[x.ss][pos];
}

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