#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;
int n, m;
struct Interval
{
int t, l, r, c;
friend bool operator < (const Interval &a, const Interval &b)
{
return a.t < b.t;
}
};
Interval a[MAXN];
std::vector <std::pair <int,llong>> g[MAXN * 60];
int nodeCounter;
struct PersistentSegmentTree
{
struct Node
{
int val;
int left;
int right;
llong edgeValue;
};
Node tree[MAXN * 30];
int root;
int cnt;
void build(int l, int r, int node, int order[])
{
if (l == r)
{
tree[node].val = order[l];
tree[node].edgeValue = INF;
return;
}
int mid = (l + r) / 2;
tree[node].left = ++cnt;
tree[node].right = ++cnt;
build(l, mid, tree[node].left, order);
build(mid + 1, r, tree[node].right, order);
tree[node].val = ++nodeCounter;
tree[node].edgeValue = 0;
g[tree[node].val].push_back({tree[tree[node].left].val, tree[tree[node].left].edgeValue});
g[tree[node].val].push_back({tree[tree[node].right].val, tree[tree[node].right].edgeValue});
}
void update(int l, int r, int newNode, int oldNode, int queryPos, int queryVal)
{
tree[newNode] = tree[oldNode];
if (l == r)
{
tree[newNode].edgeValue = queryVal;
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid)
{
tree[newNode].left = ++cnt;
update(l, mid, tree[newNode].left, tree[oldNode].left, queryPos, queryVal);
} else
{
tree[newNode].right = ++cnt;
update(mid + 1, r, tree[newNode].right, tree[oldNode].right, queryPos, queryVal);
}
tree[newNode].val = ++nodeCounter;
g[tree[newNode].val] = g[tree[oldNode].val];
g[tree[newNode].val][0] = {tree[tree[newNode].left].val, tree[tree[newNode].left].edgeValue};
g[tree[newNode].val][1] = {tree[tree[newNode].right].val, tree[tree[newNode].right].edgeValue};
}
void addEdges(int l, int r, int node, int queryL, int queryR, int from)
{
if (queryL <= l && r <= queryR)
{
g[from].push_back({tree[node].val, tree[node].edgeValue});
return;
}
int mid = (l + r) / 2;
if (queryL <= mid) addEdges(l, mid, tree[node].left, queryL, queryR, from);
if (mid + 1 <= queryR) addEdges(mid + 1, r, tree[node].right, queryL, queryR, from);
}
void build(int order[])
{
root = 1;
cnt = 1;
build(1, n, root, order);
}
void update(int pos, int val)
{
int newRoot = ++cnt;
update(1, n, newRoot, root, pos, val);
root = newRoot;
}
void addEdges(int l, int r, int from)
{
addEdges(1, n, root, l, r, from);
}
};
bool vis[MAXN];
llong dist[MAXN];
PersistentSegmentTree treePlus;
PersistentSegmentTree treeMinus;
std::priority_queue <std::pair <llong,int>> pq;
int plusOrder[MAXN];
int minusOrder[MAXN];
int inPlusOrder[MAXN];
int inMinusOrder[MAXN];
void solve()
{
std::sort(a + 1, a + 1 + n);
std::iota(plusOrder + 1, plusOrder + 1 + n, 1);
std::iota(minusOrder + 1, minusOrder + 1 + n, 1);
std::sort(plusOrder + 1, plusOrder + 1 + n, [&](int x, int y)
{
return a[x].l + a[x].t < a[y].l + a[y].t;
});
std::sort(minusOrder + 1, minusOrder + 1 + n, [&](int x, int y)
{
return a[x].l + a[x].t < a[y].l + a[y].t;
});
for (int i = 1 ; i <= n ; ++i)
{
inPlusOrder[plusOrder[i]] = i;
inMinusOrder[minusOrder[i]] = i;
}
nodeCounter = n;
treePlus.build(plusOrder);
for (int i = n ; i >= 1 ; --i)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (a[plusOrder[mid]].l + a[plusOrder[mid]].t <= a[i].r + a[i].t + 1) l = mid;
else r = mid;
}
if (l != 0)
{
treePlus.addEdges(1, l, i);
}
treePlus.update(inPlusOrder[i], a[i].c);
}
treeMinus.build(minusOrder);
for (int i = 1 ; i <= n ; ++i)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (a[minusOrder[mid]].l - a[minusOrder[mid]].t <= a[i].r - a[i].t + 1) l = mid;
else r = mid;
}
if (l != 0)
{
treeMinus.addEdges(1, l, i);
}
treeMinus.update(inMinusOrder[i], a[i].c);
}
llong ans = INF;
std::fill(dist + 1, dist + 1 + nodeCounter, INF);
for (int i = 1 ; i <= n ; ++i)
{
if (a[i].l == 1)
{
dist[i] = a[i].c;
pq.push({-dist[i], i});
}
}
while (pq.size())
{
auto [currDist, node] = pq.top();
pq.pop();
if (a[node].r == m)
{
ans = dist[node];
break;
}
if (vis[node])
{
continue;
}
vis[node] = true;
for (const auto &[u, w] : g[node])
{
if (dist[u] > dist[node] + w)
{
dist[u] = dist[node] + w;
pq.push({-dist[u], u});
}
}
}
if (ans == INF) std::cout << -1 << '\n';
else std::cout << ans << '\n';
}
void input()
{
std::cin >> m >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3135 ms |
524292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
142772 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
142816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
142772 KB |
Output is correct |
| 2 |
Incorrect |
53 ms |
142816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3135 ms |
524292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
