oj.uz

Submission #1073259

# Submission time Handle Problem Language Result Execution time Memory
1073259 2024-08-24T11:20:07 Z Sacharlemagne Train (APIO24_train) C++17
35 / 100
 122 ms 24172 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Incorrect 1 ms 348 KB Wrong Answer.
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12668 KB Correct.
2 Correct 67 ms 18476 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 8 ms 4400 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 68 ms 11856 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 42 ms 15192 KB Correct.
9 Correct 70 ms 18384 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 12668 KB Correct.
2 Correct 67 ms 18476 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Correct 8 ms 4400 KB Correct.
5 Correct 1 ms 348 KB Correct.
6 Correct 68 ms 11856 KB Correct.
7 Correct 0 ms 344 KB Correct.
8 Correct 42 ms 15192 KB Correct.
9 Correct 70 ms 18384 KB Correct.
10 Correct 113 ms 18440 KB Correct.
11 Correct 96 ms 24144 KB Correct.
12 Correct 7 ms 4444 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 91 ms 16604 KB Correct.
15 Correct 91 ms 24172 KB Correct.
16 Correct 122 ms 16980 KB Correct.
17 Correct 103 ms 21600 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct.
2 Correct 1 ms 348 KB Correct.
3 Correct 1 ms 348 KB Correct.
4 Incorrect 1 ms 348 KB Wrong Answer.
5 Halted 0 ms 0 KB -