#include <bits/stdc++.h>
using namespace std;
#define int long long
int INF = 1e18;
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int N, M; cin >> N >> M;
array<int, 4> a[M];
int c[M], p {};
bool vis[M] {};
priority_queue<array<int, 2>> q, s[2][M + 1];
for(auto &[T, L, R, C] : a) {
cin >> T >> L >> R >> C;
if(R == N) q.push({-C, p}), vis[p] = 1;
c[p++] = T;
}
sort(c, c + M);
for(int i = 0; i < M; ++i) if(!vis[i]) {
auto [T, L, R, C] = a[i];
for(int j = 0; j < 2; ++j) {
int f = R + (j ? T : -T), t = lower_bound(c, c + M, T) - c;
for(int k = (j ? t + 1 : M - t); k <= M; k += k&-k)
s[j][k].push({f, i});
}
}
int ans = INF;
while(!empty(q)) {
auto [d, u] = q.top(); q.pop();
d = -d;
auto [T, L, R, C] = a[u];
int t = lower_bound(c, c + M, T) - c;
for(int j = 0; j < 2; ++j) {
int f = L + (j ? T : -T) - 1;
for(int k = (j ? t + 1 : M - t); k > 0; k -= k&-k) {
while(1) {
while(!empty(s[j][k]) && vis[s[j][k].top()[1]])
s[j][k].pop();
if(!empty(s[j][k]) && f <= s[j][k].top()[0]) {
int v = s[j][k].top()[1]; s[j][k].pop();
vis[v] = 1;
q.push({-(d + a[v][3]), v});
} else break;
}
}
}
if(L < 2) ans = min(ans, d);
}
cout << (ans == INF ? -1 : ans);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
39604 KB |
Output is correct |
2 |
Correct |
127 ms |
42536 KB |
Output is correct |
3 |
Correct |
123 ms |
35536 KB |
Output is correct |
4 |
Correct |
125 ms |
35560 KB |
Output is correct |
5 |
Correct |
150 ms |
44668 KB |
Output is correct |
6 |
Correct |
146 ms |
42556 KB |
Output is correct |
7 |
Correct |
142 ms |
42420 KB |
Output is correct |
8 |
Correct |
103 ms |
41940 KB |
Output is correct |
9 |
Correct |
100 ms |
42396 KB |
Output is correct |
10 |
Correct |
104 ms |
42400 KB |
Output is correct |
11 |
Correct |
103 ms |
33692 KB |
Output is correct |
12 |
Correct |
103 ms |
33664 KB |
Output is correct |
13 |
Correct |
153 ms |
44820 KB |
Output is correct |
14 |
Correct |
153 ms |
44800 KB |
Output is correct |
15 |
Correct |
138 ms |
42432 KB |
Output is correct |
16 |
Correct |
137 ms |
42388 KB |
Output is correct |
17 |
Correct |
133 ms |
41656 KB |
Output is correct |
18 |
Correct |
101 ms |
32964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
316 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
316 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
316 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
316 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
9 ms |
1840 KB |
Output is correct |
21 |
Correct |
9 ms |
1876 KB |
Output is correct |
22 |
Correct |
11 ms |
2644 KB |
Output is correct |
23 |
Correct |
10 ms |
2604 KB |
Output is correct |
24 |
Correct |
10 ms |
2260 KB |
Output is correct |
25 |
Correct |
10 ms |
2116 KB |
Output is correct |
26 |
Correct |
10 ms |
2132 KB |
Output is correct |
27 |
Correct |
8 ms |
2132 KB |
Output is correct |
28 |
Correct |
10 ms |
2284 KB |
Output is correct |
29 |
Correct |
11 ms |
2156 KB |
Output is correct |
30 |
Correct |
6 ms |
2132 KB |
Output is correct |
31 |
Correct |
7 ms |
2124 KB |
Output is correct |
32 |
Correct |
8 ms |
1972 KB |
Output is correct |
33 |
Correct |
8 ms |
1836 KB |
Output is correct |
34 |
Correct |
14 ms |
2376 KB |
Output is correct |
35 |
Correct |
8 ms |
1876 KB |
Output is correct |
36 |
Correct |
7 ms |
1748 KB |
Output is correct |
37 |
Correct |
12 ms |
2240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
39604 KB |
Output is correct |
2 |
Correct |
127 ms |
42536 KB |
Output is correct |
3 |
Correct |
123 ms |
35536 KB |
Output is correct |
4 |
Correct |
125 ms |
35560 KB |
Output is correct |
5 |
Correct |
150 ms |
44668 KB |
Output is correct |
6 |
Correct |
146 ms |
42556 KB |
Output is correct |
7 |
Correct |
142 ms |
42420 KB |
Output is correct |
8 |
Correct |
103 ms |
41940 KB |
Output is correct |
9 |
Correct |
100 ms |
42396 KB |
Output is correct |
10 |
Correct |
104 ms |
42400 KB |
Output is correct |
11 |
Correct |
103 ms |
33692 KB |
Output is correct |
12 |
Correct |
103 ms |
33664 KB |
Output is correct |
13 |
Correct |
153 ms |
44820 KB |
Output is correct |
14 |
Correct |
153 ms |
44800 KB |
Output is correct |
15 |
Correct |
138 ms |
42432 KB |
Output is correct |
16 |
Correct |
137 ms |
42388 KB |
Output is correct |
17 |
Correct |
133 ms |
41656 KB |
Output is correct |
18 |
Correct |
101 ms |
32964 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
316 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
316 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
9 ms |
1840 KB |
Output is correct |
39 |
Correct |
9 ms |
1876 KB |
Output is correct |
40 |
Correct |
11 ms |
2644 KB |
Output is correct |
41 |
Correct |
10 ms |
2604 KB |
Output is correct |
42 |
Correct |
10 ms |
2260 KB |
Output is correct |
43 |
Correct |
10 ms |
2116 KB |
Output is correct |
44 |
Correct |
10 ms |
2132 KB |
Output is correct |
45 |
Correct |
8 ms |
2132 KB |
Output is correct |
46 |
Correct |
10 ms |
2284 KB |
Output is correct |
47 |
Correct |
11 ms |
2156 KB |
Output is correct |
48 |
Correct |
6 ms |
2132 KB |
Output is correct |
49 |
Correct |
7 ms |
2124 KB |
Output is correct |
50 |
Correct |
8 ms |
1972 KB |
Output is correct |
51 |
Correct |
8 ms |
1836 KB |
Output is correct |
52 |
Correct |
14 ms |
2376 KB |
Output is correct |
53 |
Correct |
8 ms |
1876 KB |
Output is correct |
54 |
Correct |
7 ms |
1748 KB |
Output is correct |
55 |
Correct |
12 ms |
2240 KB |
Output is correct |
56 |
Correct |
338 ms |
37412 KB |
Output is correct |
57 |
Correct |
336 ms |
37368 KB |
Output is correct |
58 |
Correct |
383 ms |
43188 KB |
Output is correct |
59 |
Correct |
379 ms |
43704 KB |
Output is correct |
60 |
Correct |
385 ms |
56096 KB |
Output is correct |
61 |
Correct |
375 ms |
43308 KB |
Output is correct |
62 |
Correct |
317 ms |
37424 KB |
Output is correct |
63 |
Correct |
325 ms |
44564 KB |
Output is correct |
64 |
Correct |
324 ms |
44456 KB |
Output is correct |
65 |
Correct |
163 ms |
46380 KB |
Output is correct |
66 |
Correct |
267 ms |
55844 KB |
Output is correct |
67 |
Correct |
401 ms |
45148 KB |
Output is correct |
68 |
Correct |
337 ms |
45116 KB |
Output is correct |
69 |
Correct |
296 ms |
45968 KB |
Output is correct |
70 |
Correct |
463 ms |
45352 KB |
Output is correct |
71 |
Correct |
347 ms |
45096 KB |
Output is correct |
72 |
Correct |
291 ms |
45096 KB |
Output is correct |
73 |
Correct |
457 ms |
45176 KB |
Output is correct |
74 |
Correct |
148 ms |
45084 KB |
Output is correct |
75 |
Correct |
151 ms |
45120 KB |
Output is correct |
76 |
Correct |
252 ms |
37064 KB |
Output is correct |
77 |
Correct |
259 ms |
36376 KB |
Output is correct |
78 |
Correct |
484 ms |
48304 KB |
Output is correct |
79 |
Correct |
533 ms |
44968 KB |
Output is correct |
80 |
Correct |
551 ms |
47904 KB |
Output is correct |
81 |
Correct |
241 ms |
45156 KB |
Output is correct |
82 |
Correct |
550 ms |
46232 KB |
Output is correct |
83 |
Correct |
525 ms |
44328 KB |
Output is correct |
84 |
Correct |
507 ms |
44352 KB |
Output is correct |
85 |
Correct |
362 ms |
45196 KB |
Output is correct |
86 |
Correct |
375 ms |
45040 KB |
Output is correct |
87 |
Correct |
444 ms |
45080 KB |
Output is correct |
88 |
Correct |
418 ms |
45156 KB |
Output is correct |
89 |
Correct |
419 ms |
45088 KB |
Output is correct |
90 |
Correct |
431 ms |
47804 KB |
Output is correct |
91 |
Correct |
370 ms |
46624 KB |
Output is correct |
92 |
Correct |
408 ms |
45096 KB |
Output is correct |
93 |
Correct |
534 ms |
45232 KB |
Output is correct |
94 |
Correct |
478 ms |
45340 KB |
Output is correct |
95 |
Correct |
484 ms |
45076 KB |
Output is correct |
96 |
Correct |
425 ms |
47752 KB |
Output is correct |
97 |
Correct |
432 ms |
47780 KB |
Output is correct |
98 |
Correct |
433 ms |
47804 KB |
Output is correct |
99 |
Correct |
417 ms |
47752 KB |
Output is correct |
100 |
Correct |
348 ms |
44108 KB |
Output is correct |
101 |
Correct |
420 ms |
47264 KB |
Output is correct |
102 |
Correct |
341 ms |
43844 KB |
Output is correct |
103 |
Correct |
398 ms |
45996 KB |
Output is correct |