#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int inf1 = 1e9 + 20;
const long long inf2 = 1e18L + 20;
struct planet {
int L, R;
long long cost;
planet(long long _cost): L(-2), R(-1), cost(_cost) {};
};
struct train {
int L, R, u, v;
long long cost;
train(int _L, int _R, int _u, int _v, long long _cost): L(_L), R(_R), u(_u), v(_v), cost(_cost) {};
};
struct meal {
int L, R;
meal(int _L, int _R, long long _cost): L(_L), R(_R) {};
};
struct event {
int time, type, id;
event(int _time, int _type, int _id): time(_time), type(_type), id(_id) {};
};
bool operator<(train &t1, train &t2) {
if (t1.v != t2.v) {
return t1.v < t2.v;
}
else {
return t1.R < t2.R;
}
}
bool operator<(meal &m1, meal &m2) {
return m1.R > m2.R;
}
bool operator<(event &e1, event &e2) {
if (e1.time != e2.time) {
return e1.time < e2.time;
}
else {
return e1.type < e2.type;
}
}
bool operator<(meal &m, int x) {
return m.R > x;
}
struct fenwick_tree {
vector<int> sum;
int N;
fenwick_tree(int _N) {
N = _N;
sum.resize(N + 1);
}
void update(int pos) {
pos++;
for (int i = pos; i <= N; i += i & (-i)) {
sum[i]++;
}
}
int get(int pos) {
pos++;
int res = 0;
for (int i = pos; i > 0; i -= i & (-i)) {
res += sum[i];
}
return res;
}
};
struct segment_tree {
};
long long 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<planet> planets;
for (int i = 0; i < N; i++) {
planets.emplace_back(T[i]);
}
int planet_cnt = planets.size();
vector<train> trains;
for (int i = 0; i < M; i++) {
trains.emplace_back(A[i], B[i], X[i], Y[i], C[i]);
}
trains.emplace_back(-1, 0, 0, 0, 0);
trains.emplace_back(inf1, inf1 + 1, planet_cnt - 1, planet_cnt - 1, 0);
sort(trains.begin(), trains.end());
int train_cnt = trains.size();
for (int i = 0; i < train_cnt; i++) {
if (i == 0 || trains[i].v != trains[i - 1].v) {
planets[trains[i].v].L = i;
}
if (i == train_cnt - 1 || trains[i].v != trains[i + 1].v) {
planets[trains[i].v].R = i;
}
}
vector<meal> meals;
for (int i = 0; i < W; i++) {
meals.emplace_back(L[i], R[i], T[i]);
}
sort(meals.begin(), meals.end());
int meal_cnt = meals.size();
vector<event> events;
for (int id = 0; id < train_cnt; id++) {
events.emplace_back(trains[id].L, 0, id);
}
for (int id = 0; id < meal_cnt; id++) {
events.emplace_back(meals[id].R, 1, id);
}
sort(events.begin(), events.end());
vector<long long> dp(train_cnt, inf2);
fenwick_tree fen(meal_cnt);
for (auto &e: events) {
int type = e.type;
int id = e.id;
if (type == 0) {
if (id == 0) {
dp[id] = 0;
}
else {
int u = trains[id].u;
for (int i = planets[u].L; i <= planets[u].R; i++) {
if (trains[i].R > trains[id].L) {
break;
}
int pos = lower_bound(meals.begin(), meals.end(), trains[i].R) - meals.begin() - 1;
dp[id] = min(dp[id], dp[i] + planets[u].cost * fen.get(pos) + trains[id].cost);
}
}
}
else {
fen.update(id);
}
}
long long res = dp.back();
if (res == inf2) {
res = -1;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
53 ms |
19124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
53 ms |
19124 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
