#include <bits/stdc++.h>
using namespace std;
int n, m;
// to, weight
vector<vector<pair<int, int>>> adj, adj_rev;
int add_node() {
adj.push_back({});
adj_rev.push_back({});
return adj.size() - 1;
}
void add_edge(int u, int v, int w = 0) {
if (u == 53) {
int x = 3;
}
if (u == 11 && v == 33) {
int x = 3;
}
if (u == 33 && v == 2) {
int x = 3;
}
adj[u].push_back({v, w});
adj_rev[v].push_back({u, w});
}
struct PlanNode {
int left;
int right;
PlanNode() : left(add_node()), right(add_node()) {}
};
struct Plan {
int t;
int l, r;
PlanNode node;
};
struct Seg {
int n;
vector<int> seg;
Seg(int n) : n(n), seg(2 * n, -1) {
for (int i = 0; i < 2 * n; ++i) seg[i] = add_node();
}
// add arr[i] -> node
void connect(int i, int node) {
if (i < 0) return;
i += n;
while (i > 1) {
i /= 2;
add_edge(seg[i], node);
}
}
// add node -> seg[l..r]
void connect_rev(int i, int node) {
if (i < 0) return;
i += n;
while (i > 1) {
i /= 2;
add_edge(node, seg[i]);
}
}
// add node -> arr[l..r] and update seg
void insert(int l, int r, int node) {
l += n, r += n;
while (l < r) {
if (l & 1) {
int new_node = add_node();
add_edge(node, new_node);
add_edge(seg[l], new_node);
seg[l] = new_node;
l += 1;
}
if (r & 1) {
r -= 1;
int new_node = add_node();
add_edge(node, new_node);
add_edge(seg[r], new_node);
seg[r] = new_node;
}
l /= 2, r /= 2;
}
}
// add arr[l..r] -> node and update seg
void insert_rev(int l, int r, int node) {
l += n, r += n;
while (l < r) {
if (l & 1) {
int new_node = add_node();
add_edge(new_node, node);
add_edge(new_node, seg[l]);
seg[l] = new_node;
l += 1;
}
if (r & 1) {
r -= 1;
int new_node = add_node();
add_edge(new_node, node);
add_edge(new_node, seg[r]);
seg[r] = new_node;
}
l /= 2, r /= 2;
}
}
};
vector<Plan> plans;
void solve() {
cin >> n >> m;
int source = add_node(), dest = add_node();
for (int i = 0; i < m; ++i) {
int t, l, r, cost;
cin >> t >> l >> r >> cost;
l -= 1;
PlanNode cur = PlanNode();
add_edge(cur.left, cur.right, cost);
if (l == 0) add_edge(source, cur.left);
if (r == n) add_edge(cur.right, dest);
plans.push_back({t, l, r, cur});
}
// sort by t in reverse (i.e. larger t -> first)
sort(plans.begin(), plans.end(), [&](const Plan& a, const Plan& b) { return a.t > b.t; });
// add edges for left side
vector<int> compress;
for (auto plan : plans) {
compress.push_back(plan.l - plan.t);
compress.push_back(plan.l - plan.t - 1);
compress.push_back(plan.r - plan.t);
}
sort(compress.begin(), compress.end());
compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
auto comp = [&](int tlr) { return lower_bound(compress.begin(), compress.end(), tlr) - compress.begin(); };
Seg seg(compress.size());
int j = 0;
for (auto plan : plans) {
while (j < plans.size() && plans[j].t >= plan.t) {
int seg_r = comp(plans[j].r - plans[j].t);
seg.insert(0, seg_r + 1, plans[j].node.right);
j += 1;
}
int seg_i = comp(plan.l - plan.t - 1);
seg.connect(seg_i, plan.node.left);
}
compress.clear();
for (auto plan : plans) {
compress.push_back(plan.t + plan.l);
compress.push_back(plan.t + plan.r);
compress.push_back(plan.t + plan.r + 1);
}
sort(compress.begin(), compress.end());
compress.resize(unique(compress.begin(), compress.end()) - compress.begin());
seg = Seg(compress.size());
j = 0;
for (auto plan : plans) {
while (j < plans.size() && plans[j].t >= plan.t) {
int seg_l = comp(plans[j].l + plans[j].t);
seg.insert_rev(seg_l, compress.size(), plans[j].node.left);
j += 1;
}
int seg_i = comp(plan.r + plan.t + 1);
seg.connect_rev(seg_i, plan.node.right);
}
// run dijkstra
vector<int64_t> dist(adj.size(), INT64_MAX);
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
dist[source] = 0;
pq.push({0, source});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (dist[u] < d) continue;
for (auto [v, w] : adj[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({d + w, v});
}
}
}
cout << (dist[dest] == INT64_MAX ? -1 : dist[dest]) << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
solve();
}
Compilation message
treatment.cpp: In function 'void add_edge(int, int, int)':
treatment.cpp:15:13: warning: unused variable 'x' [-Wunused-variable]
15 | int x = 3;
| ^
treatment.cpp:18:13: warning: unused variable 'x' [-Wunused-variable]
18 | int x = 3;
| ^
treatment.cpp:21:13: warning: unused variable 'x' [-Wunused-variable]
21 | int x = 3;
| ^
treatment.cpp: In function 'void solve()':
treatment.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Plan>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | while (j < plans.size() && plans[j].t >= plan.t) {
| ~~^~~~~~~~~~~~~~
treatment.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Plan>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | while (j < plans.size() && plans[j].t >= plan.t) {
| ~~^~~~~~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:193:9: warning: unused variable 't' [-Wunused-variable]
193 | int t = 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
742 ms |
524404 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
742 ms |
524404 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
