#include <cstdio>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;
#define ll long long
const ll INF = 1000000000000000000;
const int MAX_M = 100001;
int a[MAX_M], b[MAX_M], c[MAX_M], d[MAX_M];
ll dp[MAX_M], dp2[MAX_M], best[4*MAX_M], seg[13*MAX_M];
void update(int v, int tl, int tr, int pos, ll x) {
if (tl == tr) seg[v] = x;
else {
int tm = (tl+tr) >> 1;
if (pos <= tm) update(v<<1, tl, tm, pos, x);
else update(v<<1|1, tm+1, tr, pos, x);
seg[v] = min(seg[v<<1], seg[v<<1|1]);
}
}
ll query(int v, int tl, int tr, int l, int r) {
if (l > r) return INF;
if (l == tl && r == tr) return seg[v];
int tm = (tl+tr) >> 1;
return min(query(v<<1, tl, tm, l, min(r, tm)), query(v<<1|1, tm+1, tr, max(l, tm+1), r));
}
int main() {
int m, n, cur=0;
scanf("%d%d", &m, &n);
set<int> s = {1, n};
unordered_map<int, int> z;
for (int i=1; i<=m; i++) {
scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
s.insert(a[i]), s.insert(b[i]), s.insert(c[i]);
}
for (int i : s) z[i] = ++cur;
for (int i=1; i<=m; i++) a[i] = z[a[i]], b[i] = z[b[i]], c[i] = z[c[i]];
fill(&seg[0], &seg[13*MAX_M], INF);
fill(&best[0], &best[4*MAX_M], INF);
for (int i=1; i<=m; i++) update(1, 1, cur, c[i], best[c[i]] = min(best[c[i]], dp[i] = d[i] + (a[i]==1 ? 0 : query(1, 1, cur, a[i], b[i]))));
fill(&seg[0], &seg[13*MAX_M], INF);
fill(&best[0], &best[4*MAX_M], INF);
for (int i=1; i<=m; i++) update(1, 1, cur, c[i], best[c[i]] = min(best[c[i]], dp2[i] = d[i] + (b[i]==cur ? 0 : query(1, 1, cur, a[i], b[i]))));
ll ans = INF;
for (int i=1; i<=m; i++) ans = min(ans, dp[i]+dp2[i]-d[i]);
printf("%lld\n", ans == INF ? -1 : ans);
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
33 | scanf("%d%d", &m, &n);
| ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
13516 KB |
Output is correct |
2 |
Correct |
9 ms |
13608 KB |
Output is correct |
3 |
Correct |
8 ms |
13624 KB |
Output is correct |
4 |
Correct |
9 ms |
13608 KB |
Output is correct |
5 |
Correct |
9 ms |
13516 KB |
Output is correct |
6 |
Correct |
9 ms |
13516 KB |
Output is correct |
7 |
Correct |
9 ms |
13516 KB |
Output is correct |
8 |
Correct |
9 ms |
13644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
13516 KB |
Output is correct |
2 |
Correct |
9 ms |
13608 KB |
Output is correct |
3 |
Correct |
8 ms |
13624 KB |
Output is correct |
4 |
Correct |
9 ms |
13608 KB |
Output is correct |
5 |
Correct |
9 ms |
13516 KB |
Output is correct |
6 |
Correct |
9 ms |
13516 KB |
Output is correct |
7 |
Correct |
9 ms |
13516 KB |
Output is correct |
8 |
Correct |
9 ms |
13644 KB |
Output is correct |
9 |
Correct |
9 ms |
13648 KB |
Output is correct |
10 |
Correct |
9 ms |
13552 KB |
Output is correct |
11 |
Correct |
9 ms |
13612 KB |
Output is correct |
12 |
Correct |
9 ms |
13692 KB |
Output is correct |
13 |
Correct |
10 ms |
13644 KB |
Output is correct |
14 |
Correct |
9 ms |
13644 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
13516 KB |
Output is correct |
2 |
Correct |
9 ms |
13608 KB |
Output is correct |
3 |
Correct |
8 ms |
13624 KB |
Output is correct |
4 |
Correct |
9 ms |
13608 KB |
Output is correct |
5 |
Correct |
9 ms |
13516 KB |
Output is correct |
6 |
Correct |
9 ms |
13516 KB |
Output is correct |
7 |
Correct |
9 ms |
13516 KB |
Output is correct |
8 |
Correct |
9 ms |
13644 KB |
Output is correct |
9 |
Correct |
9 ms |
13648 KB |
Output is correct |
10 |
Correct |
9 ms |
13552 KB |
Output is correct |
11 |
Correct |
9 ms |
13612 KB |
Output is correct |
12 |
Correct |
9 ms |
13692 KB |
Output is correct |
13 |
Correct |
10 ms |
13644 KB |
Output is correct |
14 |
Correct |
9 ms |
13644 KB |
Output is correct |
15 |
Correct |
9 ms |
13520 KB |
Output is correct |
16 |
Correct |
10 ms |
13700 KB |
Output is correct |
17 |
Correct |
11 ms |
13800 KB |
Output is correct |
18 |
Correct |
10 ms |
13672 KB |
Output is correct |
19 |
Correct |
11 ms |
13816 KB |
Output is correct |
20 |
Correct |
11 ms |
13772 KB |
Output is correct |
21 |
Correct |
11 ms |
13772 KB |
Output is correct |
22 |
Correct |
12 ms |
14028 KB |
Output is correct |
23 |
Correct |
11 ms |
13900 KB |
Output is correct |
24 |
Correct |
11 ms |
13900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
13516 KB |
Output is correct |
2 |
Correct |
9 ms |
13608 KB |
Output is correct |
3 |
Correct |
8 ms |
13624 KB |
Output is correct |
4 |
Correct |
9 ms |
13608 KB |
Output is correct |
5 |
Correct |
9 ms |
13516 KB |
Output is correct |
6 |
Correct |
9 ms |
13516 KB |
Output is correct |
7 |
Correct |
9 ms |
13516 KB |
Output is correct |
8 |
Correct |
9 ms |
13644 KB |
Output is correct |
9 |
Correct |
9 ms |
13648 KB |
Output is correct |
10 |
Correct |
9 ms |
13552 KB |
Output is correct |
11 |
Correct |
9 ms |
13612 KB |
Output is correct |
12 |
Correct |
9 ms |
13692 KB |
Output is correct |
13 |
Correct |
10 ms |
13644 KB |
Output is correct |
14 |
Correct |
9 ms |
13644 KB |
Output is correct |
15 |
Correct |
9 ms |
13520 KB |
Output is correct |
16 |
Correct |
10 ms |
13700 KB |
Output is correct |
17 |
Correct |
11 ms |
13800 KB |
Output is correct |
18 |
Correct |
10 ms |
13672 KB |
Output is correct |
19 |
Correct |
11 ms |
13816 KB |
Output is correct |
20 |
Correct |
11 ms |
13772 KB |
Output is correct |
21 |
Correct |
11 ms |
13772 KB |
Output is correct |
22 |
Correct |
12 ms |
14028 KB |
Output is correct |
23 |
Correct |
11 ms |
13900 KB |
Output is correct |
24 |
Correct |
11 ms |
13900 KB |
Output is correct |
25 |
Correct |
34 ms |
15892 KB |
Output is correct |
26 |
Correct |
91 ms |
20036 KB |
Output is correct |
27 |
Correct |
243 ms |
27180 KB |
Output is correct |
28 |
Correct |
162 ms |
20600 KB |
Output is correct |
29 |
Correct |
181 ms |
25204 KB |
Output is correct |
30 |
Correct |
222 ms |
22212 KB |
Output is correct |
31 |
Correct |
431 ms |
35704 KB |
Output is correct |
32 |
Correct |
357 ms |
30956 KB |
Output is correct |
33 |
Correct |
63 ms |
19920 KB |
Output is correct |
34 |
Correct |
215 ms |
30728 KB |
Output is correct |
35 |
Correct |
349 ms |
48052 KB |
Output is correct |
36 |
Correct |
598 ms |
48124 KB |
Output is correct |
37 |
Correct |
495 ms |
48052 KB |
Output is correct |
38 |
Correct |
479 ms |
48176 KB |
Output is correct |