#include <bits/stdc++.h>
using namespace std;
struct project {
int t, l, r, c;
};
struct path {
int x; long long d;
path(int x, long long d): x(x), d(d) {}
bool operator < (const path &o) const {
return d > o.d;
}
};
const int N = 100005;
vector <int> tr1[N * 4], tr2[N * 4];
project prj[N]; long long dis[N];
priority_queue <path> pq;
bool cmp1(int x, int y) {
return prj[x].r + prj[x].t >= prj[y].l + prj[y].t;
};
bool cmp2(int x, int y) {
return prj[x].r - prj[x].t >= prj[y].l - prj[y].t;
};
void build(int i, int l, int r) {
if (l == r) {
tr1[i] = tr2[i] = {l}; return;
}
int m = (l + r) / 2;
build(i * 2, l, m); build(i * 2 + 1, m + 1, r);
merge(tr1[i * 2].begin(), tr1[i * 2].end(),
tr1[i * 2 + 1].begin(), tr1[i * 2 + 1].end(),
back_inserter(tr1[i]), [&](int x, int y) {
return prj[x].l + prj[x].t >= prj[y].l + prj[y].t;
});
merge(tr2[i * 2].begin(), tr2[i * 2].end(),
tr2[i * 2 + 1].begin(), tr2[i * 2 + 1].end(),
back_inserter(tr2[i]), [&](int x, int y) {
return prj[x].l - prj[x].t >= prj[y].l - prj[y].t;
});
}
void trav1(int i, int l, int r, int lim, int x) {
if (r < lim) return;
if (l >= lim) {
while (tr1[i].size()) {
int y = tr1[i].back();
if (cmp1(x, y)) {
if (dis[y] < 0) {
dis[y] = dis[x] + prj[y].c;
pq.emplace(y, dis[y]);
}
tr1[i].pop_back();
}
else break;
}
return;
}
int m = (l + r) / 2;
trav1(i * 2, l, m, lim, x);
trav1(i * 2 + 1, m + 1, r, lim, x);
}
void trav2(int i, int l, int r, int lim, int x) {
if (l > lim) return;
if (r <= lim) {
while (tr2[i].size()) {
int y = tr2[i].back();
if (cmp2(x, y)) {
if (dis[y] < 0) {
dis[y] = dis[x] + prj[y].c;
pq.emplace(y, dis[y]);
}
tr2[i].pop_back();
}
else break;
}
return;
}
int m = (l + r) / 2;
trav2(i * 2, l, m, lim, x);
trav2(i * 2 + 1, m + 1, r, lim, x);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int m, n; cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> prj[i].t >> prj[i].l >> prj[i].r >> prj[i].c;
sort(prj + 1, prj + n + 1, [](project a, project b) {
return a.t < b.t;
});
memset(dis, -1, sizeof dis); build(1, 1, n);
for (int i = 1; i <= n; i++)
if (--prj[i].l == 0)
pq.emplace(i, dis[i] = prj[i].c);
while (pq.size()) {
path t = pq.top(); pq.pop();
if (prj[t.x].r == m) {
cout << t.d << '\n'; return 0;
}
int lim = lower_bound(prj + 1, prj + n + 1, prj[t.x],
[](project a, project b) {return a.t < b.t;}) - prj;
trav1(1, 1, n, lim, t.x);
lim = upper_bound(prj + 1, prj + n + 1, prj[t.x],
[](project a, project b) {return a.t < b.t;}) - prj;
trav2(1, 1, n, lim - 1, t.x);
}
cout << "-1\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
51108 KB |
Output is correct |
2 |
Correct |
222 ms |
51256 KB |
Output is correct |
3 |
Correct |
194 ms |
51236 KB |
Output is correct |
4 |
Correct |
192 ms |
51108 KB |
Output is correct |
5 |
Correct |
180 ms |
53024 KB |
Output is correct |
6 |
Correct |
184 ms |
50980 KB |
Output is correct |
7 |
Correct |
178 ms |
51000 KB |
Output is correct |
8 |
Correct |
169 ms |
50980 KB |
Output is correct |
9 |
Correct |
166 ms |
50980 KB |
Output is correct |
10 |
Correct |
166 ms |
50980 KB |
Output is correct |
11 |
Correct |
202 ms |
53152 KB |
Output is correct |
12 |
Correct |
203 ms |
53152 KB |
Output is correct |
13 |
Correct |
199 ms |
53024 KB |
Output is correct |
14 |
Correct |
201 ms |
53152 KB |
Output is correct |
15 |
Correct |
206 ms |
51048 KB |
Output is correct |
16 |
Correct |
202 ms |
50980 KB |
Output is correct |
17 |
Correct |
196 ms |
50212 KB |
Output is correct |
18 |
Correct |
190 ms |
52384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
19948 KB |
Output is correct |
2 |
Correct |
14 ms |
19948 KB |
Output is correct |
3 |
Correct |
14 ms |
19948 KB |
Output is correct |
4 |
Correct |
14 ms |
19948 KB |
Output is correct |
5 |
Correct |
14 ms |
19948 KB |
Output is correct |
6 |
Correct |
14 ms |
19948 KB |
Output is correct |
7 |
Correct |
14 ms |
19948 KB |
Output is correct |
8 |
Correct |
15 ms |
19948 KB |
Output is correct |
9 |
Correct |
14 ms |
19948 KB |
Output is correct |
10 |
Correct |
15 ms |
19948 KB |
Output is correct |
11 |
Correct |
14 ms |
19948 KB |
Output is correct |
12 |
Correct |
14 ms |
19948 KB |
Output is correct |
13 |
Correct |
14 ms |
19948 KB |
Output is correct |
14 |
Correct |
14 ms |
19948 KB |
Output is correct |
15 |
Correct |
14 ms |
19948 KB |
Output is correct |
16 |
Correct |
14 ms |
19948 KB |
Output is correct |
17 |
Correct |
14 ms |
19948 KB |
Output is correct |
18 |
Correct |
14 ms |
19948 KB |
Output is correct |
19 |
Correct |
14 ms |
19948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
19948 KB |
Output is correct |
2 |
Correct |
14 ms |
19948 KB |
Output is correct |
3 |
Correct |
14 ms |
19948 KB |
Output is correct |
4 |
Correct |
14 ms |
19948 KB |
Output is correct |
5 |
Correct |
14 ms |
19948 KB |
Output is correct |
6 |
Correct |
14 ms |
19948 KB |
Output is correct |
7 |
Correct |
14 ms |
19948 KB |
Output is correct |
8 |
Correct |
15 ms |
19948 KB |
Output is correct |
9 |
Correct |
14 ms |
19948 KB |
Output is correct |
10 |
Correct |
15 ms |
19948 KB |
Output is correct |
11 |
Correct |
14 ms |
19948 KB |
Output is correct |
12 |
Correct |
14 ms |
19948 KB |
Output is correct |
13 |
Correct |
14 ms |
19948 KB |
Output is correct |
14 |
Correct |
14 ms |
19948 KB |
Output is correct |
15 |
Correct |
14 ms |
19948 KB |
Output is correct |
16 |
Correct |
14 ms |
19948 KB |
Output is correct |
17 |
Correct |
14 ms |
19948 KB |
Output is correct |
18 |
Correct |
14 ms |
19948 KB |
Output is correct |
19 |
Correct |
14 ms |
19948 KB |
Output is correct |
20 |
Correct |
24 ms |
21504 KB |
Output is correct |
21 |
Correct |
24 ms |
21468 KB |
Output is correct |
22 |
Correct |
24 ms |
21484 KB |
Output is correct |
23 |
Correct |
23 ms |
21484 KB |
Output is correct |
24 |
Correct |
22 ms |
21484 KB |
Output is correct |
25 |
Correct |
25 ms |
21484 KB |
Output is correct |
26 |
Correct |
25 ms |
21612 KB |
Output is correct |
27 |
Correct |
28 ms |
21596 KB |
Output is correct |
28 |
Correct |
25 ms |
21484 KB |
Output is correct |
29 |
Correct |
25 ms |
21484 KB |
Output is correct |
30 |
Correct |
21 ms |
21484 KB |
Output is correct |
31 |
Correct |
21 ms |
21484 KB |
Output is correct |
32 |
Correct |
21 ms |
21612 KB |
Output is correct |
33 |
Correct |
21 ms |
21484 KB |
Output is correct |
34 |
Correct |
25 ms |
21484 KB |
Output is correct |
35 |
Correct |
21 ms |
21484 KB |
Output is correct |
36 |
Correct |
21 ms |
21624 KB |
Output is correct |
37 |
Correct |
27 ms |
21356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
51108 KB |
Output is correct |
2 |
Correct |
222 ms |
51256 KB |
Output is correct |
3 |
Correct |
194 ms |
51236 KB |
Output is correct |
4 |
Correct |
192 ms |
51108 KB |
Output is correct |
5 |
Correct |
180 ms |
53024 KB |
Output is correct |
6 |
Correct |
184 ms |
50980 KB |
Output is correct |
7 |
Correct |
178 ms |
51000 KB |
Output is correct |
8 |
Correct |
169 ms |
50980 KB |
Output is correct |
9 |
Correct |
166 ms |
50980 KB |
Output is correct |
10 |
Correct |
166 ms |
50980 KB |
Output is correct |
11 |
Correct |
202 ms |
53152 KB |
Output is correct |
12 |
Correct |
203 ms |
53152 KB |
Output is correct |
13 |
Correct |
199 ms |
53024 KB |
Output is correct |
14 |
Correct |
201 ms |
53152 KB |
Output is correct |
15 |
Correct |
206 ms |
51048 KB |
Output is correct |
16 |
Correct |
202 ms |
50980 KB |
Output is correct |
17 |
Correct |
196 ms |
50212 KB |
Output is correct |
18 |
Correct |
190 ms |
52384 KB |
Output is correct |
19 |
Correct |
15 ms |
19948 KB |
Output is correct |
20 |
Correct |
14 ms |
19948 KB |
Output is correct |
21 |
Correct |
14 ms |
19948 KB |
Output is correct |
22 |
Correct |
14 ms |
19948 KB |
Output is correct |
23 |
Correct |
14 ms |
19948 KB |
Output is correct |
24 |
Correct |
14 ms |
19948 KB |
Output is correct |
25 |
Correct |
14 ms |
19948 KB |
Output is correct |
26 |
Correct |
15 ms |
19948 KB |
Output is correct |
27 |
Correct |
14 ms |
19948 KB |
Output is correct |
28 |
Correct |
15 ms |
19948 KB |
Output is correct |
29 |
Correct |
14 ms |
19948 KB |
Output is correct |
30 |
Correct |
14 ms |
19948 KB |
Output is correct |
31 |
Correct |
14 ms |
19948 KB |
Output is correct |
32 |
Correct |
14 ms |
19948 KB |
Output is correct |
33 |
Correct |
14 ms |
19948 KB |
Output is correct |
34 |
Correct |
14 ms |
19948 KB |
Output is correct |
35 |
Correct |
14 ms |
19948 KB |
Output is correct |
36 |
Correct |
14 ms |
19948 KB |
Output is correct |
37 |
Correct |
14 ms |
19948 KB |
Output is correct |
38 |
Correct |
24 ms |
21504 KB |
Output is correct |
39 |
Correct |
24 ms |
21468 KB |
Output is correct |
40 |
Correct |
24 ms |
21484 KB |
Output is correct |
41 |
Correct |
23 ms |
21484 KB |
Output is correct |
42 |
Correct |
22 ms |
21484 KB |
Output is correct |
43 |
Correct |
25 ms |
21484 KB |
Output is correct |
44 |
Correct |
25 ms |
21612 KB |
Output is correct |
45 |
Correct |
28 ms |
21596 KB |
Output is correct |
46 |
Correct |
25 ms |
21484 KB |
Output is correct |
47 |
Correct |
25 ms |
21484 KB |
Output is correct |
48 |
Correct |
21 ms |
21484 KB |
Output is correct |
49 |
Correct |
21 ms |
21484 KB |
Output is correct |
50 |
Correct |
21 ms |
21612 KB |
Output is correct |
51 |
Correct |
21 ms |
21484 KB |
Output is correct |
52 |
Correct |
25 ms |
21484 KB |
Output is correct |
53 |
Correct |
21 ms |
21484 KB |
Output is correct |
54 |
Correct |
21 ms |
21624 KB |
Output is correct |
55 |
Correct |
27 ms |
21356 KB |
Output is correct |
56 |
Correct |
246 ms |
51364 KB |
Output is correct |
57 |
Correct |
246 ms |
51812 KB |
Output is correct |
58 |
Correct |
258 ms |
50468 KB |
Output is correct |
59 |
Correct |
260 ms |
50596 KB |
Output is correct |
60 |
Correct |
301 ms |
51364 KB |
Output is correct |
61 |
Correct |
256 ms |
50340 KB |
Output is correct |
62 |
Correct |
249 ms |
51492 KB |
Output is correct |
63 |
Correct |
237 ms |
51108 KB |
Output is correct |
64 |
Correct |
241 ms |
51108 KB |
Output is correct |
65 |
Correct |
199 ms |
51364 KB |
Output is correct |
66 |
Correct |
265 ms |
51236 KB |
Output is correct |
67 |
Correct |
422 ms |
51876 KB |
Output is correct |
68 |
Correct |
361 ms |
51748 KB |
Output is correct |
69 |
Correct |
347 ms |
51748 KB |
Output is correct |
70 |
Correct |
438 ms |
51876 KB |
Output is correct |
71 |
Correct |
389 ms |
51748 KB |
Output is correct |
72 |
Correct |
340 ms |
51748 KB |
Output is correct |
73 |
Correct |
418 ms |
51876 KB |
Output is correct |
74 |
Correct |
191 ms |
51748 KB |
Output is correct |
75 |
Correct |
186 ms |
51748 KB |
Output is correct |
76 |
Correct |
207 ms |
53512 KB |
Output is correct |
77 |
Correct |
200 ms |
52772 KB |
Output is correct |
78 |
Correct |
306 ms |
53408 KB |
Output is correct |
79 |
Correct |
442 ms |
52004 KB |
Output is correct |
80 |
Correct |
445 ms |
51364 KB |
Output is correct |
81 |
Correct |
202 ms |
51748 KB |
Output is correct |
82 |
Correct |
421 ms |
50596 KB |
Output is correct |
83 |
Correct |
418 ms |
50724 KB |
Output is correct |
84 |
Correct |
431 ms |
51108 KB |
Output is correct |
85 |
Correct |
305 ms |
51748 KB |
Output is correct |
86 |
Correct |
306 ms |
51748 KB |
Output is correct |
87 |
Correct |
343 ms |
51748 KB |
Output is correct |
88 |
Correct |
312 ms |
51748 KB |
Output is correct |
89 |
Correct |
328 ms |
51748 KB |
Output is correct |
90 |
Correct |
201 ms |
53792 KB |
Output is correct |
91 |
Correct |
197 ms |
51748 KB |
Output is correct |
92 |
Correct |
324 ms |
51748 KB |
Output is correct |
93 |
Correct |
388 ms |
51748 KB |
Output is correct |
94 |
Correct |
386 ms |
51876 KB |
Output is correct |
95 |
Correct |
335 ms |
51748 KB |
Output is correct |
96 |
Correct |
200 ms |
52900 KB |
Output is correct |
97 |
Correct |
203 ms |
53792 KB |
Output is correct |
98 |
Correct |
205 ms |
53792 KB |
Output is correct |
99 |
Correct |
202 ms |
53792 KB |
Output is correct |
100 |
Correct |
197 ms |
53920 KB |
Output is correct |
101 |
Correct |
222 ms |
53792 KB |
Output is correct |
102 |
Correct |
201 ms |
53920 KB |
Output is correct |
103 |
Correct |
275 ms |
51748 KB |
Output is correct |