제출 #1287049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287049		modwwe	은하철도 (APIO24_train)	C++20	100 / 100	403 ms	90508 KiB

train

#pragma GCC optimize("Ofast,unroll-loops")
#include "train.h"
#include <bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "facttree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const ll inf = 1e17;
const int mod2 = 998244353;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
                                                               r2, center;
int  i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
int el = 19;
struct ib {
    ll a, b;
};
vector<ll> dp[100007], dp2[100007], vc[100007], gl, gr, vx[100007], vd[100007];
vector<ib> dc, hihi;
int base = 0;
struct id {
    ll l, r;
};
struct ic {
    ll a, b, c;
};
vector<vector<ic>>v[100007];
int f[100007], t[100007];
bool cmp(ib x, ib y) {
    return x.a < y.a;
}
bool cmk(ib x, ib y) {
    return x.b < y.b;
}
struct perseg {
    ll t[6000001];
    id cur[6000001];
    int upd(int u, int l, int r, int x) {
        int v = ++dem;

        if (l == r) {
            t[v] = t[u] + 1;
            return v;
        }

        int mid = l + r >> 1;
        cur[v] = cur[u];

        if (x <= mid)
            cur[v].l = upd(cur[u].l, l, mid, x);
        else
            cur[v].r = upd(cur[u].r, mid + 1, r, x);

        t[v] = t[cur[v].l] + t[cur[v].r];
        return v;
    }
    ll get(int u, int l, int r, int l1, int r1) {
        if (l > r1 || r < l1)
            return 0;

        if (l >= l1 && r <= r1)
            return t[u];

        int mid = l + r >> 1;
        return get(cur[u].l, l, mid, l1, r1) + get(cur[u].r, mid + 1, r, l1, r1);
    }
    int walk(int u, int v, int l, int r, ll x, ll y, ll ggg) {
        if (l == r)
            return l;

        int mid = l + r >> 1;

        if (t[cur[u].l]*ggg + x >= t[cur[v].l]*ggg + y)
            return walk(cur[u].l, cur[v].l, l, mid, x, y, ggg);

        return walk(cur[u].r, cur[v].r, mid + 1, r, x + t[cur[u].l] * ggg, y + t[cur[v].l] * ggg, ggg);
    }
} st;
ll cost(int x, int y, int z) {
    return dp2[x][y] + st.get(f[upper_bound(gl.begin(), gl.end(), vc[x][y]) - gl.begin()], -1, gr.size(), 1,
                              lower_bound(gr.begin(), gr.end(), vc[x][z]) - gr.begin()) * t[x];
}
void huff(int x, int y) {
    if (vd[x].size() == 0)
        return;

    int kk = lower_bound(gr.begin(), gr.end(), vc[x][y]) - gr.begin();
    int hihi = upper_bound(vd[x].begin(), vd[x].end(), kk) - vd[x].begin() - 1;
    int ff = vx[x][hihi];
    dp[x][y] = min(dp[x][y], cost(x, ff, y));
}
int fx(int x, int y, int z) {
    int k1 = upper_bound(gl.begin(), gl.end(), vc[x][y]) - gl.begin();
    int k2 = upper_bound(gl.begin(), gl.end(), vc[x][z]) - gl.begin();

    if (dp2[x][y] + st.t[f[k1]]*t[x] < dp2[x][z] + st.t[f[k2]]*t[x])
        return -2;

    return st.walk(f[k1], f[k2], -1, gr.size(), dp2[x][y], dp2[x][z], t[x]);
}
void buff(int x, int y) {
    int nxt = 0;

    while (true) {
        if (vx[x].size() == 0)
            break;

        int hihi = vx[x].back();
        int gf = fx(x, hihi, y);
        nxt = gf;

        if (gf >= vd[x].back() || nxt == -2)
            break;

        vx[x].pop_back();
        vd[x].pop_back();
    }

    if (nxt != -2) {
        if (vx[x].size() == 0)
            nxt = 0;

        vx[x].pb(y);
        vd[x].pb(nxt);
    }
}
ll solve(int N, int M, int K, vector<int> T, vector<int> X, vector<int> Y, vector<int> a, vector<int> b,
         vector<int> c, vector<int> fl, vector<int> fr) {
    n = N;
    m = M;
    k = K;

    for (int i = 1; i <= n; i++)
        t[i] = T[i - 1];

    dc.pb({1, -1});
    vc[1].pb({-1});
    vc[n].pb({inf});
    dc.pb({n, inf});

    /*
    for(int i=1; i<=m; i++)
        cin>>X[i];
    for(int i=1; i<=m; i++)
        cin>>Y[i];
    for(int i=1; i<=m; i++)
        cin>>a[i];
    for(int i=1; i<=m; i++)
        cin>>b[i];
    for(int i=1; i<=m; i++)
        cin>>c[i];*/
    for (int i = 0; i < m; i++) {
        //cin>>X[i]>>Y[i]>>a[i]>>b[i]>>c[i];
        X[i]++;
        Y[i]++;
        vc[X[i]].pb(a[i]);
        vc[Y[i]].pb(b[i]);
        dc.pb({X[i], a[i]});
        dc.pb({Y[i], b[i]});
    }/*

    for(int i=1; i<=k; i++)
        cin>>fl[i];
    for(int i=1; i<=k; i++)
        cin>>fr[i];*/
    gl.pb(inf + 1);
    gr.pb(inf + 1);
    hihi.pb({inf + 1, inf + 1});

    for (int i = 1; i <= k; i++) {
        l = fl[i - 1];
        r = fr[i - 1];
        gl.pb(l);
        gr.pb(r);
        hihi.pb({l, r});
    }

    sort(hihi.begin(), hihi.end(), cmp);
    sort(gl.begin(), gl.end());
    sort(gr.begin(), gr.end());
    gr.erase(unique(gr.begin(), gr.end()), gr.end());

    for (int i = gl.size() - 1; i >= 0; --i) {
        base = st.upd(base, -1, gr.size(), lower_bound(gr.begin(), gr.end(), hihi[i].b) - gr.begin() + 1);
        f[i] = base;
    }

    for (int i = 1; i <= n; i++) {
        if (vc[i].size()) {
            sort(vc[i].begin(), vc[i].end());
            vc[i].erase(unique(vc[i].begin(), vc[i].end()), vc[i].end());
            v[i].resize(vc[i].size());
            dp[i].resize(vc[i].size());
            dp2[i].resize(vc[i].size());

            for (int j = 0; j < dp[i].size(); j++)
                dp[i][j] = dp2[i][j] = inf;
        }
    }

    for (int i = 0; i < m; i++) {
        v[X[i]][lower_bound(vc[X[i]].begin(), vc[X[i]].end(), a[i]) - vc[X[i]].begin()]
        .pb({Y[i], lower_bound(vc[Y[i]].begin(), vc[Y[i]].end(), b[i]) - vc[Y[i]].begin(), c[i]});
    }

    sort(dc.begin(), dc.end(), cmk);
    dp2[1][0] = 0;
    dp[1][0] = 0;

    for (auto x : dc) {
        x.b = lower_bound(vc[x.a].begin(), vc[x.a].end(), x.b) - vc[x.a].begin();
        huff(x.a, x.b);
        buff(x.a, x.b);

        for (auto y : v[x.a][x.b]) {
            dp2[y.a][y.b] = min(dp2[y.a][y.b], min(dp2[x.a][x.b], dp[x.a][x.b]) + y.c);
            dp[y.a][y.b] = min(dp[y.a][y.b], dp2[y.a][y.b]);
        }
    }

    if (min(dp2[n].back(), dp[n].back()) == inf)
        return -1;
    else
        return min(dp2[n].back(), dp[n].back());
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60