#include "train.h"
#include <bits/stdc++.h>
namespace Kth {
struct Wavelet {
int min, max;
std::vector<int> pfx;
Wavelet *left, *right;
Wavelet(int l, int r, std::vector<int> &stuff) : min(l), max(r) {
if (stuff.empty()) return;
if (max == min + 1) {
left = right = nullptr;
return;
}
int mid = (min + max) / 2;
int s = 0;
std::vector<int> L, R;
for (auto x: stuff) {
if (x < mid) {
s++;
L.push_back(x);
} else {
R.push_back(x);
}
pfx.push_back(s);
}
stuff.clear();
left = new Wavelet(min, mid, L);
right = new Wavelet(mid, max, R);
}
int query(int l, int r, int k) {//Return value of kth (0-indexed) largest in [l,r]
if (max == min + 1) return min;
int numInRange = pfx[r];
if (l) numInRange -= pfx[l];
if (numInRange > k) {
return left->query(l ? pfx[l - 1] : 0, r ? pfx[r - 1] : 0, k);
} else {
return right->query(l ? l - pfx[l - 1] : 0, r ? r - pfx[r - 1] : 0, k);
}
}
};
}
struct Compressor {
std::vector<int> stuff;
std::map<int, int> res;
void run() {
std::sort(stuff.begin(), stuff.end());
stuff.erase(std::unique(stuff.begin(), stuff.end()), stuff.end());
for (int i = 0; i < stuff.size(); ++i) {
res[stuff[i]] = i;
}
stuff.clear();
}
void operator+=(int x) {
stuff.push_back(x);
}
int operator[](int x) {
return res[x];
}
};
struct node {
int min, max;
node *left, *right;
int value;
node(int l, int r) {
min = l;
max = r;
left = right = nullptr;
value = 0;
}
void add(int l, int r) {
l = std::max(l, min);
r = std::min(r, max);
if (l >= max || r <= min) return;
if (l == min && r == max) {
value++;
return;
}
if (!left) {
left = new node(min, (min + max) / 2);
right = new node((min + max) / 2, max);
}
left->add(l, r);
right->add(l, r);
}
int query(int x) const {
if (x < min || x >= max) return 0;
return value + (left ? (left->query(x) + right->query(x)) : 0);
}
};
long long
solve(int nodes, int edges, int meals, std::vector<int> mealCost, std::vector<int> start, std::vector<int> end,
std::vector<int> startTime, std::vector<int> endTime, std::vector<int> cost, std::vector<int> mealStart,
std::vector<int> mealEnd) {
{
Compressor c;
c += -1;
for (int i = 0; i < edges; ++i) {
c += startTime[i];
c += endTime[i];
}
for (int i = 0; i < meals; ++i) {
c += mealStart[i];
c += mealEnd[i];
}
c.run();
for (int i = 0; i < edges; ++i) {
startTime[i] = c[startTime[i]];
endTime[i] = c[endTime[i]];
}
for (int i = 0; i < meals; ++i) {
mealStart[i] = c[mealStart[i]];
mealEnd[i] = c[mealEnd[i]];
}
}
//All times are now in [0, 400000]
node tree(0, 400001);
std::vector<std::pair<int, int>> current[nodes];//{pos, cost}
current[0].emplace_back(0, 0);
struct event {
int time;
int idx;
bool departure;
bool meal;
};
std::vector<event> events;
for (int i = 0; i < edges; ++i) {
events.push_back({startTime[i], i, true, false});
events.push_back({endTime[i], i, false, false});
}
for (int i = 0; i < meals; ++i) {
events.push_back({mealEnd[i], i, false, true});
}
std::sort(events.begin(), events.end(), [&](event a, event b) {
if (a.time == b.time && a.meal == b.meal) return a.departure < b.departure;
if (a.time == b.time) return a.meal < b.meal;
return a.time < b.time;
});
auto getBest = [&](int node) {
long long ans = LONG_LONG_MAX;
for (auto [p, c]: current[node]) {
ans = std::min(ans, c + ((long long) tree.query(p)) * mealCost[node]);
}
return ans;
};
long long edgeTime[edges];
for (auto [time, idx, depart, meal]: events) {
if (meal) {
tree.add(0, mealStart[idx]);
} else if (depart) {
edgeTime[idx] = getBest(start[idx]);
if (edgeTime[idx] != LONG_LONG_MAX) {
edgeTime[idx] += cost[idx];
}
} else {
if (edgeTime[idx] != LONG_LONG_MAX)
current[end[idx]].emplace_back(time, edgeTime[idx]);
}
}
auto res = getBest(nodes - 1);
if (res == LONG_LONG_MAX) return -1;
return res;
}
Compilation message
train.cpp: In member function 'void Compressor::run()':
train.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0; i < stuff.size(); ++i) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Correct. |
| 2 |
Correct |
1 ms |
348 KB |
Correct. |
| 3 |
Correct |
1 ms |
348 KB |
Correct. |
| 4 |
Correct |
1 ms |
348 KB |
Correct. |
| 5 |
Correct |
0 ms |
348 KB |
Correct. |
| 6 |
Correct |
1 ms |
344 KB |
Correct. |
| 7 |
Correct |
0 ms |
348 KB |
Correct. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
14776 KB |
Integer -1986450113 violates the range [-1, 10^18] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
14776 KB |
Integer -1986450113 violates the range [-1, 10^18] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Correct. |
| 2 |
Correct |
1 ms |
348 KB |
Correct. |
| 3 |
Correct |
1 ms |
348 KB |
Correct. |
| 4 |
Correct |
1 ms |
348 KB |
Correct. |
| 5 |
Correct |
0 ms |
348 KB |
Correct. |
| 6 |
Correct |
1 ms |
344 KB |
Correct. |
| 7 |
Correct |
0 ms |
348 KB |
Correct. |
| 8 |
Incorrect |
120 ms |
14776 KB |
Integer -1986450113 violates the range [-1, 10^18] |
| 9 |
Halted |
0 ms |
0 KB |
- |
