Submission #1165016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165016		vladilius	Train (APIO24_train)	C++20	100 / 100	462 ms	192152 KiB

train

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;
const int A = 1e9;

struct PST{
    struct node{
        node *l, *r;
        int k;
        node(int x){
            l = r = 0;
            k = x;
        }
        node(node *ls, node *rs){
            l = ls; r = rs;
            k = 0;
            if (l) k += l -> k;
            if (r) k += r -> k;
        }
    };
    vector<node*> root;
    vector<int> f = {0}, pp;
    int n, m, cc;
    vector<int> :: iterator it;
    PST(int ns, int ms, vector<int> ps){
        n = ns; m = ms; pp = ps;
        root.resize(m + 1);
        root[0] = build(1, n);
        cc = 0;
    }
    node* build(int tl, int tr){
        if (tl == tr) return new node(0);
        int tm = (tl + tr) / 2;
        return new node(build(tl, tm), build(tm + 1, tr));
    }
    node* upd(node *v, int tl, int tr, int x){
        if (tl == tr) return new node(v -> k + 1);
        int tm = (tl + tr) / 2;
        if (x <= tm){
            return new node(upd(v -> l, tl, tm, x), v -> r);
        }
        else {
            return new node(v -> l, upd(v -> r, tm + 1, tr, x));
        }
    }
    void upd(int x, int y){
        f.pb(y);
        it = upper_bound(pp.begin() + 1, pp.end(), x); it--;
        x = (int) (it - pp.begin());
        cc++;
        root[cc] = upd(root[cc - 1], 1, n, x);
    }
    int get(node *v, int tl, int tr, int l, int r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return v -> k;
        int tm = (tl + tr) / 2;
        return get(v -> l, tl, tm, l, r) + get(v -> r, tm + 1, tr, l, r);
    }
    int F(int l, int r){
        l++; r--;
        if (l > r) return 0;
        it = upper_bound(f.begin() + 1, f.end(), r); it--;
        r = (int) (it - f.begin());
 
        it = lower_bound(pp.begin() + 1, pp.end(), l);
        l = (int) (it - pp.begin());
        return get(root[r], 1, n, l, n);
    }
    int kth(node *vr, node *vl, int tl, int tr, ll k){
        if (tl == tr) return pp[tl];
        int tm = (tl + tr) / 2, cc = vr -> l -> k - vl -> l -> k;
        if (cc >= k) return kth(vr -> l, vl -> l, tl, tm, k);
        return kth(vr -> r, vl -> r, tm + 1, tr, k - cc);
    }
    int G(int l, int r, ll k){
        l++;
        if (l > r) return A;
        
        it = upper_bound(f.begin() + 1, f.end(), r); it--;
        r = (int) (it - f.begin());
        
        it = upper_bound(f.begin() + 1, f.end(), l - 1); it--;
        l = (int) (it - f.begin());
        
        if ((root[r] -> k - root[l] -> k) < k) return A;
        return kth(root[r], root[l], 1, n, k);
    }
};

ll solve(int n, int m, int w, vector<int> t, vector<int> x, vector<int> y, vector<int> a, vector<int> b, vector<int> c, vector<int> l, vector<int> r){
    vector<pii> d;
    for (int i = 0; i < m; i++){
        d.pb({b[i], i});
    }

    sort(d.begin(), d.end());

    vector<int> na(m), nb(m), nc(m), nx(m), ny(m);
    for (int i = 0; i < m; i++){
        int j = d[i].ss;
        na[i] = a[j];
        nb[i] = b[j];
        nc[i] = c[j];
        nx[i] = x[j];
        ny[i] = y[j];
    }

    a = na; b = nb; c = nc; x = nx; y = ny;

    vector<int> g[n + 1];
    for (int i = 0; i < m; i++){
        x[i]++; y[i]++;
        g[y[i]].pb(i);
    }

    t.insert(t.begin(), 0);
    
    vector<pii> all;
    for (int i = 0; i < w; i++){
        all.pb({l[i], r[i]});
    }
    
    auto cmp1 = [&](pii x, pii y){
        return x.ss < y.ss;
    };
    
    sort(all.begin(), all.end(), cmp1);
    
    vector<int> pp = {0};
    for (auto [x, y]: all){
        pp.pb(x); pp.pb(y);
    }
    for (int i = 0; i < m; i++){
        pp.pb(b[i]);
    }
    
    sort(pp.begin(), pp.end());
    
    int N = (int) pp.size();
    PST T(N, (int) all.size(), pp);
    for (auto [x, y]: all){
        T.upd(x, y);
    }

    auto f = [&](int l, int r){
        return T.F(l, r);
    };
    
    PST F(N, (int) all.size(), pp);
    sort(all.begin(), all.end());
    for (auto [x, y]: all){
        F.upd(y, x);
    }
    
    auto G = [&](int l, int r, ll k){
        if (k <= 0) return 0;
        return F.G(l, r, k);
    };
    
    vector<pii> ed;
    for (int i = 0; i < m; i++){
        ed.pb({a[i], i});
    }
    sort(ed.begin(), ed.end());
    
    vector<ll> dp(m);
    vector<int> s(n + 1);
    
    set<int> st[n + 1];
    priority_queue<pii, vector<pii>, greater<pii>> pq[n + 1];
    
    ll out = inf;
    for (auto [B, i]: ed){
        int v = x[i];
        while (s[v] < g[v].size() && b[g[v][s[v]]] <= a[i]){
            int x = g[v][s[v]];
            if (st[v].empty()){
                st[v].insert(x);
                s[v]++;
                continue;
            }
            int y = *prev(st[v].end());
            pq[v].push({G(b[y], b[x], ceil(1.0 * (dp[x] - dp[y]) / t[v])), y});
            st[v].insert(x); s[v]++;
        }
        
        while (!pq[v].empty() && pq[v].top().ff < a[i]){
            auto [x, y] = pq[v].top(); pq[v].pop();
            if (st[v].find(y) == st[v].end()) continue;
            auto it = st[v].find(y);
            if (it != prev(st[v].end()) && it != st[v].begin()){
                int y1 = *next(it), y2 = *prev(it);
                pq[v].push({G(b[y2], b[y1], ceil(1.0 * (dp[y1] - dp[y2]) / t[v])), y2});
            }
            st[v].erase(y);
        }
        
        ll mn = inf;
        if (!st[v].empty()){
            int x = *st[v].begin();
            mn = dp[x] + 1LL * t[v] * f(b[x], a[i]);
        }
        if (x[i] == 1) mn = min(mn, 1LL * t[v] * f(0, a[i]));
        dp[i] = mn + c[i];

        if (y[i] == n){
            out = min(out, dp[i] + 1LL * t[n] * f(b[i], A + 1));
        }
    }

    if (out == inf) return -1;
    return out;
}

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