#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
typedef long long ll;
using namespace std;
const int maxm = 1 << 17;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > st[2][maxm * 2];
vector<int> cm[2]; // skomprimovane x suradnice
ll dist[maxm]; // vzdialenosti
int n, m;
void update(int ly, int x, int y, int i)
{
x = lower_bound(cm[ly].begin(), cm[ly].end(), x) - cm[ly].begin();
for (x += maxm; x > 0; x >>= 1)
st[ly][x].push({ y, i });
}
vector<int> v;
void query(int ly, int x, int y)
{
x = lower_bound(cm[ly].begin(), cm[ly].end(), x) - cm[ly].begin();
for (int r = x + maxm + 1; r > 0; r >>= 1) if (r & 1)
{
r--;
while (!st[ly][r].empty() && st[ly][r].top().first <= y)
{
int i = st[ly][r].top().second; st[ly][r].pop();
if (!dist[i]) v.push_back(i);
}
}
}
struct project { int t, l, r, c; } p[maxm];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > mini;
for (int i = 0; i < m; i++)
{
cin >> p[i].t >> p[i].l >> p[i].r >> p[i].c, p[i].l--;
if (!p[i].l) mini.push({ p[i].c, i }), dist[i] = p[i].c;
cm[0].push_back(-p[i].t), cm[1].push_back(p[i].t);
}
for (int l = 0; l < 2; l++)
{
sort(cm[l].begin(), cm[l].end());
for (int i = 0; i < m; i++) update(l, (l == 0 ? -p[i].t : p[i].t), (l == 0 ? p[i].l + p[i].t : p[i].l - p[i].t), i);
}
while (!mini.empty())
{
int i = mini.top().second;
mini.pop();
if (p[i].r == n)
{
cout << dist[i] << "\n";
return 0;
}
v.clear();
query(0, -p[i].t, p[i].r + p[i].t);
query(1, p[i].t, p[i].r - p[i].t);
for (int j : v) if (!dist[j])
{
//cout << i << " -> " << j << "\n";
dist[j] = dist[i] + (ll)p[j].c;
mini.push({ dist[j], j });
}
}
cout << "-1\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
53228 KB |
Output is correct |
2 |
Correct |
196 ms |
56352 KB |
Output is correct |
3 |
Correct |
205 ms |
55908 KB |
Output is correct |
4 |
Correct |
231 ms |
55868 KB |
Output is correct |
5 |
Correct |
194 ms |
57892 KB |
Output is correct |
6 |
Correct |
211 ms |
56344 KB |
Output is correct |
7 |
Correct |
228 ms |
56268 KB |
Output is correct |
8 |
Correct |
165 ms |
56292 KB |
Output is correct |
9 |
Correct |
162 ms |
55824 KB |
Output is correct |
10 |
Correct |
162 ms |
55480 KB |
Output is correct |
11 |
Correct |
201 ms |
58336 KB |
Output is correct |
12 |
Correct |
207 ms |
58440 KB |
Output is correct |
13 |
Correct |
206 ms |
57448 KB |
Output is correct |
14 |
Correct |
228 ms |
57400 KB |
Output is correct |
15 |
Correct |
225 ms |
56300 KB |
Output is correct |
16 |
Correct |
217 ms |
56304 KB |
Output is correct |
17 |
Correct |
227 ms |
55536 KB |
Output is correct |
18 |
Correct |
201 ms |
57576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
16744 KB |
Output is correct |
2 |
Correct |
10 ms |
16716 KB |
Output is correct |
3 |
Correct |
10 ms |
16716 KB |
Output is correct |
4 |
Correct |
10 ms |
16652 KB |
Output is correct |
5 |
Correct |
12 ms |
16732 KB |
Output is correct |
6 |
Correct |
13 ms |
16716 KB |
Output is correct |
7 |
Correct |
10 ms |
16716 KB |
Output is correct |
8 |
Correct |
10 ms |
16716 KB |
Output is correct |
9 |
Correct |
10 ms |
16748 KB |
Output is correct |
10 |
Correct |
10 ms |
16740 KB |
Output is correct |
11 |
Correct |
10 ms |
16696 KB |
Output is correct |
12 |
Correct |
10 ms |
16716 KB |
Output is correct |
13 |
Correct |
10 ms |
16712 KB |
Output is correct |
14 |
Correct |
10 ms |
16744 KB |
Output is correct |
15 |
Correct |
11 ms |
16644 KB |
Output is correct |
16 |
Correct |
11 ms |
16716 KB |
Output is correct |
17 |
Correct |
11 ms |
16716 KB |
Output is correct |
18 |
Correct |
10 ms |
16716 KB |
Output is correct |
19 |
Correct |
10 ms |
16716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
16744 KB |
Output is correct |
2 |
Correct |
10 ms |
16716 KB |
Output is correct |
3 |
Correct |
10 ms |
16716 KB |
Output is correct |
4 |
Correct |
10 ms |
16652 KB |
Output is correct |
5 |
Correct |
12 ms |
16732 KB |
Output is correct |
6 |
Correct |
13 ms |
16716 KB |
Output is correct |
7 |
Correct |
10 ms |
16716 KB |
Output is correct |
8 |
Correct |
10 ms |
16716 KB |
Output is correct |
9 |
Correct |
10 ms |
16748 KB |
Output is correct |
10 |
Correct |
10 ms |
16740 KB |
Output is correct |
11 |
Correct |
10 ms |
16696 KB |
Output is correct |
12 |
Correct |
10 ms |
16716 KB |
Output is correct |
13 |
Correct |
10 ms |
16712 KB |
Output is correct |
14 |
Correct |
10 ms |
16744 KB |
Output is correct |
15 |
Correct |
11 ms |
16644 KB |
Output is correct |
16 |
Correct |
11 ms |
16716 KB |
Output is correct |
17 |
Correct |
11 ms |
16716 KB |
Output is correct |
18 |
Correct |
10 ms |
16716 KB |
Output is correct |
19 |
Correct |
10 ms |
16716 KB |
Output is correct |
20 |
Correct |
26 ms |
18804 KB |
Output is correct |
21 |
Correct |
27 ms |
18804 KB |
Output is correct |
22 |
Correct |
26 ms |
19244 KB |
Output is correct |
23 |
Correct |
25 ms |
19276 KB |
Output is correct |
24 |
Correct |
25 ms |
19060 KB |
Output is correct |
25 |
Correct |
27 ms |
18988 KB |
Output is correct |
26 |
Correct |
27 ms |
19008 KB |
Output is correct |
27 |
Correct |
27 ms |
18932 KB |
Output is correct |
28 |
Correct |
30 ms |
19108 KB |
Output is correct |
29 |
Correct |
26 ms |
19000 KB |
Output is correct |
30 |
Correct |
23 ms |
18892 KB |
Output is correct |
31 |
Correct |
20 ms |
18932 KB |
Output is correct |
32 |
Correct |
24 ms |
19060 KB |
Output is correct |
33 |
Correct |
25 ms |
19100 KB |
Output is correct |
34 |
Correct |
30 ms |
19136 KB |
Output is correct |
35 |
Correct |
27 ms |
19020 KB |
Output is correct |
36 |
Correct |
24 ms |
19128 KB |
Output is correct |
37 |
Correct |
30 ms |
18968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
226 ms |
53228 KB |
Output is correct |
2 |
Correct |
196 ms |
56352 KB |
Output is correct |
3 |
Correct |
205 ms |
55908 KB |
Output is correct |
4 |
Correct |
231 ms |
55868 KB |
Output is correct |
5 |
Correct |
194 ms |
57892 KB |
Output is correct |
6 |
Correct |
211 ms |
56344 KB |
Output is correct |
7 |
Correct |
228 ms |
56268 KB |
Output is correct |
8 |
Correct |
165 ms |
56292 KB |
Output is correct |
9 |
Correct |
162 ms |
55824 KB |
Output is correct |
10 |
Correct |
162 ms |
55480 KB |
Output is correct |
11 |
Correct |
201 ms |
58336 KB |
Output is correct |
12 |
Correct |
207 ms |
58440 KB |
Output is correct |
13 |
Correct |
206 ms |
57448 KB |
Output is correct |
14 |
Correct |
228 ms |
57400 KB |
Output is correct |
15 |
Correct |
225 ms |
56300 KB |
Output is correct |
16 |
Correct |
217 ms |
56304 KB |
Output is correct |
17 |
Correct |
227 ms |
55536 KB |
Output is correct |
18 |
Correct |
201 ms |
57576 KB |
Output is correct |
19 |
Correct |
11 ms |
16744 KB |
Output is correct |
20 |
Correct |
10 ms |
16716 KB |
Output is correct |
21 |
Correct |
10 ms |
16716 KB |
Output is correct |
22 |
Correct |
10 ms |
16652 KB |
Output is correct |
23 |
Correct |
12 ms |
16732 KB |
Output is correct |
24 |
Correct |
13 ms |
16716 KB |
Output is correct |
25 |
Correct |
10 ms |
16716 KB |
Output is correct |
26 |
Correct |
10 ms |
16716 KB |
Output is correct |
27 |
Correct |
10 ms |
16748 KB |
Output is correct |
28 |
Correct |
10 ms |
16740 KB |
Output is correct |
29 |
Correct |
10 ms |
16696 KB |
Output is correct |
30 |
Correct |
10 ms |
16716 KB |
Output is correct |
31 |
Correct |
10 ms |
16712 KB |
Output is correct |
32 |
Correct |
10 ms |
16744 KB |
Output is correct |
33 |
Correct |
11 ms |
16644 KB |
Output is correct |
34 |
Correct |
11 ms |
16716 KB |
Output is correct |
35 |
Correct |
11 ms |
16716 KB |
Output is correct |
36 |
Correct |
10 ms |
16716 KB |
Output is correct |
37 |
Correct |
10 ms |
16716 KB |
Output is correct |
38 |
Correct |
26 ms |
18804 KB |
Output is correct |
39 |
Correct |
27 ms |
18804 KB |
Output is correct |
40 |
Correct |
26 ms |
19244 KB |
Output is correct |
41 |
Correct |
25 ms |
19276 KB |
Output is correct |
42 |
Correct |
25 ms |
19060 KB |
Output is correct |
43 |
Correct |
27 ms |
18988 KB |
Output is correct |
44 |
Correct |
27 ms |
19008 KB |
Output is correct |
45 |
Correct |
27 ms |
18932 KB |
Output is correct |
46 |
Correct |
30 ms |
19108 KB |
Output is correct |
47 |
Correct |
26 ms |
19000 KB |
Output is correct |
48 |
Correct |
23 ms |
18892 KB |
Output is correct |
49 |
Correct |
20 ms |
18932 KB |
Output is correct |
50 |
Correct |
24 ms |
19060 KB |
Output is correct |
51 |
Correct |
25 ms |
19100 KB |
Output is correct |
52 |
Correct |
30 ms |
19136 KB |
Output is correct |
53 |
Correct |
27 ms |
19020 KB |
Output is correct |
54 |
Correct |
24 ms |
19128 KB |
Output is correct |
55 |
Correct |
30 ms |
18968 KB |
Output is correct |
56 |
Correct |
610 ms |
56612 KB |
Output is correct |
57 |
Correct |
628 ms |
57084 KB |
Output is correct |
58 |
Correct |
663 ms |
55328 KB |
Output is correct |
59 |
Correct |
679 ms |
55860 KB |
Output is correct |
60 |
Correct |
590 ms |
66404 KB |
Output is correct |
61 |
Correct |
643 ms |
55392 KB |
Output is correct |
62 |
Correct |
650 ms |
56628 KB |
Output is correct |
63 |
Correct |
573 ms |
59236 KB |
Output is correct |
64 |
Correct |
595 ms |
59152 KB |
Output is correct |
65 |
Correct |
236 ms |
57256 KB |
Output is correct |
66 |
Correct |
571 ms |
65968 KB |
Output is correct |
67 |
Correct |
576 ms |
59924 KB |
Output is correct |
68 |
Correct |
503 ms |
59796 KB |
Output is correct |
69 |
Correct |
469 ms |
60476 KB |
Output is correct |
70 |
Correct |
687 ms |
60140 KB |
Output is correct |
71 |
Correct |
554 ms |
59816 KB |
Output is correct |
72 |
Correct |
466 ms |
59740 KB |
Output is correct |
73 |
Correct |
671 ms |
59928 KB |
Output is correct |
74 |
Correct |
266 ms |
59308 KB |
Output is correct |
75 |
Correct |
248 ms |
59028 KB |
Output is correct |
76 |
Correct |
489 ms |
65164 KB |
Output is correct |
77 |
Correct |
498 ms |
61912 KB |
Output is correct |
78 |
Correct |
662 ms |
65080 KB |
Output is correct |
79 |
Correct |
830 ms |
59800 KB |
Output is correct |
80 |
Correct |
813 ms |
62628 KB |
Output is correct |
81 |
Correct |
472 ms |
59200 KB |
Output is correct |
82 |
Correct |
865 ms |
61940 KB |
Output is correct |
83 |
Correct |
858 ms |
59060 KB |
Output is correct |
84 |
Correct |
845 ms |
59140 KB |
Output is correct |
85 |
Correct |
646 ms |
59820 KB |
Output is correct |
86 |
Correct |
658 ms |
59904 KB |
Output is correct |
87 |
Correct |
813 ms |
59896 KB |
Output is correct |
88 |
Correct |
781 ms |
59916 KB |
Output is correct |
89 |
Correct |
794 ms |
59768 KB |
Output is correct |
90 |
Correct |
602 ms |
63132 KB |
Output is correct |
91 |
Correct |
562 ms |
59120 KB |
Output is correct |
92 |
Correct |
726 ms |
59904 KB |
Output is correct |
93 |
Correct |
841 ms |
59924 KB |
Output is correct |
94 |
Correct |
801 ms |
60076 KB |
Output is correct |
95 |
Correct |
716 ms |
59768 KB |
Output is correct |
96 |
Correct |
474 ms |
61800 KB |
Output is correct |
97 |
Correct |
513 ms |
62992 KB |
Output is correct |
98 |
Correct |
529 ms |
62076 KB |
Output is correct |
99 |
Correct |
540 ms |
62896 KB |
Output is correct |
100 |
Correct |
535 ms |
62656 KB |
Output is correct |
101 |
Correct |
570 ms |
62256 KB |
Output is correct |
102 |
Correct |
536 ms |
63364 KB |
Output is correct |
103 |
Correct |
585 ms |
60296 KB |
Output is correct |