#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);
}
};
struct countnode {
int min, max;
countnode *left, *right;
int value;
countnode(int l, int r) {
min = l;
max = r;
left = right = nullptr;
value = 0;
}
void add(int x) {
if (x < min || x >= max) return;
value++;
if (max == min + 1) return;
if (!left) {
left = new countnode(min, (min + max) / 2);
right = new countnode((min + max) / 2, max);
}
left->add(x);
right->add(x);
}
int query(int l, int r) const {
l = std::max(l, min);
r = std::min(r, max);
if (l >= max || r <= min) return 0;
if (l == min && r == max) return value;
if (!left) return 0;
return left->query(l, r) + right->query(l, r);
}
};
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);
countnode countTree(0, 400001);
for (int i = 0; i < meals; ++i) {
countTree.add(mealStart[i]);
}
std::vector<std::pair<int, int>> stuff;
for (int i = 0; i < meals; ++i) {
stuff.emplace_back(mealStart[i], mealEnd[i]);
}
std::sort(stuff.begin(), stuff.end());
std::vector<int> Stuff;
for (auto [a, b]: stuff) {
Stuff.push_back(b);
}
Kth::Wavelet kth(0, 400001, Stuff);
std::deque<std::pair<int, long long>> 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 overTake = [&](int p1, int p2, long long diff, int cost) {//Diff = cost[p2]-cost[p1]
if (diff <= 0) return 0;
if (p1 == p2) return INT_MAX;
if (cost == 0) return INT_MAX;
long long needed = (diff + cost - 1) / cost;//As soon as *at least* needed, go
if (countTree.query(p1 + 1, p2 + 1) < needed) return INT_MAX;
int lidx = countTree.query(0, p1 + 1);
int ridx = countTree.query(0, p2 + 1) - 1;
return kth.query(lidx, ridx, needed - 1);
};
auto score = [&](int p, long long c, int node) {
return c + ((long long) tree.query(p)) * mealCost[node];
};
const long long INF = LONG_LONG_MAX / 2;
auto getBest = [&](int node) {
while (current[node].size() > 1 && score(current[node][0].first, current[node][0].second, node) >=
score(current[node][1].first, current[node][1].second, node)) {
current[node].pop_front();
}
if (current[node].empty()) return INF;
return score(current[node][0].first, current[node][0].second, node);
};
auto add = [&](int node, int p, long long c) {
while (((!current[node].empty()) &&
score(p, c, node) <= score(current[node].back().first, current[node].back().second, node)) ||
(current[node].size() > 1 &&
overTake(p, current[node].back().first, c - current[node].back().second, mealCost[node]) <=
overTake(current[node][current[node].size() - 2].first, current[node].back().first,
current[node].back().second - current[node][current[node].size() - 2].second,
mealCost[node]))) {
current[node].pop_back();
}
current[node].emplace_front(p, c);
};
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] != INF) {
edgeTime[idx] += cost[idx];
}
} else {
if (edgeTime[idx] != INF)
add(end[idx], time, edgeTime[idx]);
// current[end[idx]].emplace_back(time, edgeTime[idx]);
}
}
auto res = getBest(nodes - 1);
if (res == INF) return -1ll;
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 |
Incorrect |
1 ms |
344 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
17640 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
17640 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
