Submission #1077038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077038		Trent	Overtaking (IOI23_overtaking)	C++17	100 / 100	2118 ms	454516 KiB

overtaking

#include "overtaking.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
#define asst(x) if(!(x)) exit(2)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
struct bus {
    ll t; int w;
};
struct ivl {
    ll l, r, ans;
};
vvll t, e, me;
vi pos;
int X;

struct segTree {
    struct node {
        ll val;
        bool lz;
    };
    vector<node> seg;
    vll inds; // in segment tree, val = inds[i] -> i -> 2*i + 1
    int cl, cr;
    segTree(vll& vals) {
        inds = vals;
        int els = vals.size() * 2 + 1;
        seg = vector<node>(4 * els, {-1, false});
        cl = 0;
        cr = els - 1;
    }
    void push(int v, int l, int r) {
        if(l < r) {
            if(seg[v].lz) {
                seg[2*v].val = seg[v].val, seg[2*v+1].val = seg[v].val;
                seg[2*v].lz = seg[2*v+1].lz = true;
                seg[v].lz = false;
                seg[v].val = -1;
            }
        }
    }
    void upd(int v, int nl, int nr, int l, int r, ll to) {
        asst(l >= nl && r <= nr);
        push(v, nl, nr);
        if(l > r) return;
        if(nl == l && nr == r) {
            seg[v].val = to;
            seg[v].lz = true;
        } else {
            int mid = (nl+nr)/2;
            upd(2*v, nl, mid, l, min(r, mid), to);
            upd(2*v+1, mid+1, nr, max(mid+1, l), r, to);
        }
    }
    ll qu(int v, int nl, int nr, int i) {
        asst(i >= nl && i <= nr);
        push(v, nl, nr);
        if(nl == i && nr == i) return seg[v].val;
        int mid = (nl+nr)/2;
        if(i <= mid) return qu(2*v, nl, mid, i);
        return qu(2*v+1, mid+1, nr, i);
    }
    int binSearch(ll val) {
        auto nv = lower_bound(all(this->inds), val);
        if(nv == inds.end()) return (int) inds.size() * 2;
        if(*nv == val) return 2 * (nv - inds.begin()) + 1;
        return 2 * (nv - inds.begin());
    }
    void upd(ll l, ll r, ll to) {
        upd(1, cl, cr, binSearch(l), binSearch(r), to);
    }
    ll qu(ll i) {
        return qu(1, cl, cr, binSearch(i));
    }
};
segTree* seg = nullptr;

void sortByTime(vector<bus>& bs) {
    sort(all(bs), [](bus a, bus b){return a.t < b.t;});
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    vll nt; vi nw;
    set<int> rem;
    forR(i, N) if(W[i] <= X) rem.insert(i);
    forR(i, N) if(!rem.count(i)) {
        nt.push_back(T[i]);
        nw.push_back(W[i]);
    }
    N -= rem.size();
    T = nt, W = nw;

    t = vvll(M, vll(N)), e = vvll(M-1, vll(N)), me = vvll(M-1, vll(N));
    pos = S;
    vector<bus> bs;
    forR(i, N) {
        bs.push_back({T[i], W[i]});
    }
    forR(i, M-1) {
        sortByTime(bs);
        forR(j, N) t[i][j] = bs[j].t;
        forR(j, N) e[i][j] = bs[j].t + (ll) bs[j].w * (S[i+1] - S[i]);
        ll cm = 0;
        for(int j = 0; j < N; ){
            ll cur = bs[j].t;
            int k=j;
            for(; k < N && bs[k].t == cur; ++k) {}
            REP(l, j, k) bs[l].t = max(e[i][l], cm);
            REP(l, j, k) cm = max(cm, e[i][l]);
            j = k;
        }
    }
    forR(j, N) t[M-1][j] = bs[j].t;
    ::X = X;
    forR(i, M-1) {
        if(N > 0) me[i][0] = e[i][0];
        REP(j, 1, N) me[i][j] = max(e[i][j], me[i][j-1]);
    }

    vll inds;
    for(int i = M-2; i >= 0; --i) {
        ll toNex = (ll) X * (S[i+1]-S[i]), toHere = (ll) X * (S[i] - S[0]);
        forR(j, N) {
            ll lo = t[i][j]+1;
            ll hi = j == N-1 ? me[i][j] - toNex : min(me[i][j] - toNex, t[i][j+1]);
            ll find = me[i][j] - toNex - toHere;

            ll nlo = lo - toHere, nhi = hi - toHere;
            inds.push_back(nlo);
            inds.push_back(nhi);
            inds.push_back(find);
        }
    }
    sort(all(inds));
    seg = new segTree(inds);

    for(int i = M-2; i >= 0; --i) {
        ll toNex = (ll) X * (S[i+1]-S[i]), toHere = (ll) X * (S[i] - S[0]);
        forR(j, N) {
            ll lo = t[i][j]+1;
            ll hi = j == N-1 ? me[i][j] - toNex : min(me[i][j] - toNex, t[i][j+1]);

            ll nlo = lo - toHere, nhi = hi - toHere;
            ll find = me[i][j] - toNex - toHere;
            ll ans = seg->qu(find);
            if(ans == -1) ans = me[i][j] + (ll) X * (S[M-1] - S[i+1]);
            seg->upd(nlo, nhi, ans);
        }
    }
}

long long arrival_time(long long Y)
{
    int M = (int) pos.size(), N = t[0].size();
    ll ans = seg->qu(Y);
    if(ans == -1) ans = Y + (ll) X * (pos[M-1] - pos[0]);
    return ans;
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:160:31: warning: unused variable 'N' [-Wunused-variable]
  160 |     int M = (int) pos.size(), N = t[0].size();
      |                               ^

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