Submission #1073259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073259		Sacharlemagne	Train (APIO24_train)	C++17	35 / 100	122 ms	24172 KiB

train

#include "train.h"

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
const ll INF = 4e18;
vll finishes, starts;
#define x first
#define y second
ll endsBef(ll time) {
    return lower_bound(finishes.begin(), finishes.end(), time)-finishes.begin();
}
ll startBef(ll time) {
    return lower_bound(starts.begin(), starts.end(), time) - starts.begin();
}


struct edge {
    ll from,to,l,r,cost;
};
struct update {
    pll now;
    ll time;
    ll node;

    bool operator<(const update& u) const {
        return time > u.time;
    }
};

bool cmp(const edge &a, const edge &b) {
    return a.l < b.l;
}


ll cost(pll cur, ll mealsBef, ll price) {
    ll mealsToBuy = max(0ll,mealsBef - cur.y);
    ll addCost = mealsToBuy * price;
    return cur.x + addCost;
}


long long solve(int N, int M, int W, vi T, vi X, vi Y,
                vi A, vi B, vi C, vi L,
                vi R) {

    finishes.resize(W); for (int i = 0; i<W; ++i) finishes[i] = R[i]; sort(finishes.begin(), finishes.end());
    starts.resize(W); for (int i = 0; i<W; ++i) starts[i] = L[i]; sort(starts.begin(), starts.end());
    vector<edge> edges(M);
    vector<vector<pll>> upto(N);
    vector<int> ind(N, 0);
    upto[0].push_back({0,0});

    for (int i = 0; i<M; ++i) {
        edges[i] = {X[i], Y[i], A[i], B[i], C[i]};
    }

    sort(edges.begin(), edges.end(), cmp);
    priority_queue<update, vector<update>> pq;
    for (edge e : edges) {
        while (!pq.empty() && pq.top().time <= e.l) {
            pll now = pq.top().now;
            ll u = pq.top().node;
            pq.pop();
            if (!upto[u].empty() && upto[u].back().x >= now.x) {
                upto[u].clear();
            }
            if (upto[u].empty()) {
                upto[u] = {now};
                ind[u] = 0;
                continue;
            }
            else if (upto[u].back().y < now.y) {
                ll dif = T[u] * (now.y - upto[u].back().y);
                if (upto[u].back().x + dif > now.x) {
                    upto[u].push_back(now);
                }
            }
            else if (upto[u].back().y > now.y) {
                return 0;
            }
        }
        ll node = e.from, u = e.to, l = e.l, r = e.r;
        if (upto[node].empty()) continue;
        ll mealsBef = endsBef(l);
        while (ind[node] < upto[node].size()-1) {
            ll curCost = cost(upto[node][ind[node]], mealsBef, T[node]);
            ll costAf = cost(upto[node][ind[node]+1], mealsBef, T[node]);
            if (costAf < curCost) ++ind[node];
            else break;
        }
        ll addCost = cost(upto[node][ind[node]], mealsBef, T[node]);
        ll totCost = addCost + e.cost;
        pll now = {totCost, startBef(r+1)};
        pq.push({now, r, u});
    }
    ll ans = INF;
    while (!pq.empty()) {
        pll now = pq.top().now;
        ll u = pq.top().node;
        pq.pop();
        if (u != N-1) continue;
        ans = min(ans, cost(now, W, T[N-1]));
    }
    for (pll p : upto[N-1]) {
        ans = min(ans, cost(p, W, T[N-1]));
    }
    if (ans == INF) return -1;
    return ans;
}

Compilation message (stderr)

train.cpp: In function 'long long int solve(int, int, int, vi, vi, vi, vi, vi, vi, vi, vi)':
train.cpp:89:26: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         while (ind[node] < upto[node].size()-1) {

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