Submission #1074977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074977		mickey080929	Overtaking (IOI23_overtaking)	C++17	100 / 100	1398 ms	54812 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf = 4e18 + 10;

struct Line{
    ll a, b;
    ll id;
};

bool cmp(Line l1, Line l2, ll x) {
    ll t1 = (x-l1.a) / l1.b, t2 = (x-l2.a) / l2.b;
    if (t1 == t2) return ((x-l1.a)-t1*l1.b) * l2.b < ((x-l2.a)-t2*l2.b) * l1.b;
    return t1 < t2;
}

struct Node{
    ll l, r;
    Line line;
};

struct LiChaoTree{
    vector<Node> tree;
    void init() {
        tree.clear();
        tree.push_back({-1, -1, {-inf, 1, -1}});
    }
    void update(ll node, ll s, ll e, Line p) {
        Line lo = tree[node].line;
        Line hi = p;
        if (cmp(hi, lo, s)) swap(lo, hi);
        if (!cmp(hi, lo, e)) {
            tree[node].line = lo;
            return;
        }
        ll mid = (s + e) / 2;
        if (!cmp(hi, lo, mid)) {
            tree[node].line = lo;
            if (tree[node].r == -1) {
                tree[node].r = tree.size();
                tree.push_back({-1, -1, {-inf, 1, -1}});
            }
            update(tree[node].r, mid+1, e, hi);
        }
        else {
            tree[node].line = hi;
            if (tree[node].l == -1) {
                tree[node].l = tree.size();
                tree.push_back({-1, -1, {-inf, 1, -1}});
            }
            update(tree[node].l, s, mid, lo);
        }
    }
    Line query(ll node, ll s, ll e, ll x) {
        if (node == -1) return {-inf, 1, -1};
        if (s == e) return tree[node].line;
        ll mid = (s + e) / 2;
        if (x <= mid) {
            Line t = query(tree[node].l, s, mid, x);
            if (cmp(t, tree[node].line, x)) return t;
            return tree[node].line;
        }
        Line t = query(tree[node].r, mid+1, e, x);
        if (cmp(t, tree[node].line, x)) return t;
        return tree[node].line;
    }
};

LiChaoTree seg;
LiChaoTree seg2[1010];

vector<ll> t1;

int N, M;
ll L, X;
vector<ll> T, W, S;

ll arr[1010][1010];
ll st[1010][1010];

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S)
{
    L = _L;
    X = _X;
    M = _M;
    for (int i=0; i<M; i++) {
        S.push_back(_S[i]);
    }
    for (int i=0; i<_N; i++) {
        if (_W[i] > X) {
            T.push_back(_T[i]);
            W.push_back(_W[i]);
            N ++;
        }
    }

    for (int i=0; i<N; i++) {
        arr[0][i] = T[i];
    }
    for (int i=1; i<M; i++) {
        vector<int> id(N);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&] (int &u, int &v) {
            if (arr[i-1][u] == arr[i-1][v])
                return W[u] < W[v];
            return arr[i-1][u] < arr[i-1][v];
        });
        ll mx = 0;
        for (auto &j : id) {
            arr[i][j] = max(mx, arr[i-1][j] + W[j] * (S[i] - S[i-1]));
            mx = max(mx, arr[i][j]);
        }
    }
    for (int i=M-1; i>=0; i--) {
        vector<int> id(N);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&] (int &u, int &v) {
            return arr[i][u] < arr[i][v];
        });
        seg.init();
        int p = 0;
        for (int j=0; j<N; j++) {
            if (j == 0) {
                st[i][id[j]] = arr[i][id[j]] + (L - S[i]) * X;
            }
            else {
                ll cross = seg.query(0, 0, inf, arr[i][id[j]]).id;
                assert(cross != -1);
                ll pos = S[i] + (arr[i][id[j]] - arr[i][cross] + W[cross] - X - 1) / (W[cross] - X);
                if (pos > L) {
                    st[i][id[j]] = arr[i][id[j]] + (L - S[i]) * X;
                }
                else {
                    ll idx = lower_bound(S.begin(), S.end(), pos) - S.begin();
                    st[i][id[j]] = st[idx][cross];
                }
            }
            seg.update(0, 0, inf, {arr[i][id[j]], W[id[j]] - X, id[j]});
        }
    }
    vector<int> id(N);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&] (int &u, int &v) { return T[u] < T[v]; });
    for (int i=0; i<=N; i++) {
        seg2[i].init();
        for (int j=0; j<i; j++) {
            seg2[i].update(0, 0, inf, {T[id[j]], W[id[j]] - X, id[j]});
        }
    }
    t1 = T;
    sort(t1.begin(), t1.end());

    return;
}

long long arrival_time(long long Y)
{
    ll idx = lower_bound(t1.begin(), t1.end(), Y) - t1.begin();
    if (idx == 0) return Y + X * L;
    ll cross = seg2[idx].query(0, 0, inf, Y).id;
    assert(cross != -1);
    ll pos = (Y - T[cross] + W[cross] - X - 1) / (W[cross] - X);
    if (pos > L) return Y + X * L;
    ll idx2 = lower_bound(S.begin(), S.end(), pos) - S.begin();
    assert(st[idx2][cross] >= Y);
    return st[idx2][cross];
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:129:13: warning: unused variable 'p' [-Wunused-variable]
  129 |         int p = 0;
      |             ^

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