Submission #1164979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164979		vladilius	Train (APIO24_train)	C++20	0 / 100	39 ms	7860 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;

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<int> g[n + 1];
    for (int i = 0; i < m; i++){
        x[i]++; y[i]++;
        g[y[i]].pb(i);
    }
    
    auto cmp = [&](int x, int y){
        return b[x] < b[y];
    };
    
    for (int i = 1; i <= n; i++){
        sort(g[i].begin(), g[i].end(), cmp);
    }
    
    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);
    
    auto f = [&](int l, int r){
        int out = 0;
        for (auto [x, y]: all){
            out += (l < x && y < r);
        }
        return out;
    };
    
    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);
    
    auto G = [&](int l, int r, ll k){
        if (k <= 0) return 0;
        int cc = 0;
        for (auto [x, y]: all){
            if (cc == k) return y;
            cc += (l < x && x <= r);
        }
        return A;
    };
    
    set<pii> 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]];
            for (auto [T, y]: st[v]){
                pq[v].push({G(b[y], b[x], ceil(1.0 * (dp[x] - dp[y] / t[v]))), y});
                pq[v].push({G(b[x], b[y], ceil(1.0 * (dp[y] - dp[x] / t[v]))), x});
            }
            st[v].insert({b[x], x});
            s[v]++;
        }
        
        while (!pq[v].empty() && pq[v].top().ff < a[i]){
            auto [x, y] = pq[v].top(); pq[v].pop();
            auto it = st[v].find({b[y], y});
            if (it != st[v].end()){
                st[v].erase({b[y], y});
            }
        }
        
        ll mn = inf;
        for (auto [T, x]: st[v]){
            mn = min(mn, dp[x] + 1LL * t[v] * f(b[x], a[i]));
        }

        if (!st[v].empty()){
            auto [T, x] = *st[v].begin();
            ll F = dp[x] + 1LL * t[v] * f(b[x], a[i]);
            assert(mn == F);
        }


        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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60