#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int l2 = 2e9 + 10;
struct SegmentTree {
int n;
vector<pair<int, int>> t;
vector<multiset<pair<int, int>>> mst;
SegmentTree(int _n) {
n = _n;
t.assign(4 * n, {l2, l2});
mst.resize(n + 1);
}
void update(int x, int lx, int rx, int i, pair<int, int> v, bool erase) {
if (lx == rx) {
if (erase) mst[lx].erase(mst[lx].find(v));
else mst[lx].insert(v);
if (mst[lx].empty()) t[x] = {l2, l2};
else t[x] = *mst[lx].begin();
return;
}
int mx = (lx + rx) >> 1;
if (i <= mx) update(x << 1, lx, mx, i, v, erase);
else update(x << 1 | 1, mx + 1, rx, i, v, erase);
t[x] = min(t[x << 1], t[x << 1 | 1]);
}
pair<int, int> query(int x, int lx, int rx, int l, int r) {
if (l > rx || lx > r || l > r) return {l2, l2};
if (l <= lx && r >= rx) return t[x];
int mx = (lx + rx) >> 1;
return min(query(x << 1, lx, mx, l, r), query(x << 1 | 1, mx + 1, rx, l, r));
}
};
void testCase() {
int n, m;
cin >> n >> m;
vector<int> t(m), l(m), r(m), c(m), all, tt(m);
for (int i = 0; i < m; i++) {
cin >> t[i] >> l[i] >> r[i] >> c[i];
all.push_back(t[i]);
}
sort(all.begin(), all.end());
for (int i = 0; i < m; i++) {
tt[i] = lower_bound(all.begin(), all.end(), t[i]) - all.begin() + 1;
}
SegmentTree st1(n), st2(n);
for (int i = 0; i < m; i++) {
st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, false);
st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, false);
}
priority_queue<pair<ll, int>> pq;
vector<bool> vis(m);
vector<ll> dist(m, inf);
for (int i = 0; i < m; i++) {
if (l[i] == 1) {
st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, true);
st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, true);
dist[i] = c[i];
pq.push({-dist[i], i});
}
}
while (!pq.empty()) {
auto [_, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = true;
auto q = st1.query(1, 1, m, 1, tt[u]);
while (q.first <= r[u] - t[u] + 1) {
auto [v, i] = q;
st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, true);
st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, true);
dist[i] = dist[u] + c[i];
pq.push({-dist[i], i});
q = st1.query(1, 1, m, 1, tt[u]);
}
q = st2.query(1, 1, m, tt[u], m);
while (q.first <= r[u] + t[u] + 1) {
auto [v, i] = q;
st1.update(1, 1, m, tt[i], {l[i] - t[i], i}, true);
st2.update(1, 1, m, tt[i], {l[i] + t[i], i}, true);
dist[i] = dist[u] + c[i];
pq.push({-dist[i], i});
q = st2.query(1, 1, m, tt[u], m);
}
}
ll ans = inf;
for (int i = 0; i < m; i++) {
if (r[i] == n) ans = min(ans, dist[i]);
}
cout << (ans == inf ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
8696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
604 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
33 ms |
8696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
