#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 1e5 + 7, C = 3 * N, INF = 1e18 + 7;
int m, n;
struct Seg { int l, r, p, c; } a[N];
vector <int> c;
int pos(int x) { return lower_bound(all(c), x) - c.begin(); }
void upd(int v, int tl, int tr, int p, int x, int *tree) {
if (tl == tr) { tree[v] = min(tree[v], x); return; }
int tm = (tl + tr) >> 1;
if (p <= tm) upd(v * 2 + 1, tl, tm, p, x, tree);
else upd(v * 2 + 2, tm + 1, tr, p, x, tree);
tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}
int get(int v, int tl, int tr, int l, int r, int *tree) {
if (tr < l || r < tl) return INF;
if (l <= tl && tr <= r) return tree[v];
int tm = (tl + tr) >> 1;
return min(get(v * 2 + 1, tl, tm, l, r, tree), get(v * 2 + 2, tm + 1, tr, l, r, tree));
}
int dp[N][2], tree[2][C << 2];
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
for (int i = 0; i < 2; ++i) for (int j = 0; j < (C << 2); ++j) tree[i][j] = INF;
cin >> m >> n;
c.app(1); c.app(n);
for (int i = 0; i < m; ++i) { cin >> a[i].l >> a[i].r >> a[i].p >> a[i].c; c.app(a[i].l); c.app(a[i].r); c.app(a[i].p); }
sort(all(c)); c.resize(unique(all(c)) - c.begin());
upd(0, 0, C, 0, 0, tree[0]); upd(0, 0, C, (int)c.size() - 1, 0, tree[1]);
int ans = INF;
for (int i = 0; i < m; ++i) {
a[i].l = pos(a[i].l); a[i].r = pos(a[i].r); a[i].p = pos(a[i].p);
for (int j = 0; j < 2; ++j) {
dp[i][j] = get(0, 0, C, a[i].l, a[i].r, tree[j]) + a[i].c;
upd(0, 0, C, a[i].p, dp[i][j], tree[j]);
}
ans = min(ans, dp[i][0] + dp[i][1] - a[i].c);
}
if (ans == INF) cout << "-1\n";
else cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19192 KB |
Output is correct |
2 |
Correct |
17 ms |
19192 KB |
Output is correct |
3 |
Correct |
18 ms |
19192 KB |
Output is correct |
4 |
Correct |
17 ms |
19064 KB |
Output is correct |
5 |
Correct |
17 ms |
19064 KB |
Output is correct |
6 |
Correct |
17 ms |
19192 KB |
Output is correct |
7 |
Correct |
17 ms |
19192 KB |
Output is correct |
8 |
Correct |
17 ms |
19192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19192 KB |
Output is correct |
2 |
Correct |
17 ms |
19192 KB |
Output is correct |
3 |
Correct |
18 ms |
19192 KB |
Output is correct |
4 |
Correct |
17 ms |
19064 KB |
Output is correct |
5 |
Correct |
17 ms |
19064 KB |
Output is correct |
6 |
Correct |
17 ms |
19192 KB |
Output is correct |
7 |
Correct |
17 ms |
19192 KB |
Output is correct |
8 |
Correct |
17 ms |
19192 KB |
Output is correct |
9 |
Correct |
17 ms |
19192 KB |
Output is correct |
10 |
Correct |
18 ms |
19192 KB |
Output is correct |
11 |
Correct |
18 ms |
19164 KB |
Output is correct |
12 |
Correct |
18 ms |
19164 KB |
Output is correct |
13 |
Correct |
18 ms |
19192 KB |
Output is correct |
14 |
Correct |
18 ms |
19208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19192 KB |
Output is correct |
2 |
Correct |
17 ms |
19192 KB |
Output is correct |
3 |
Correct |
18 ms |
19192 KB |
Output is correct |
4 |
Correct |
17 ms |
19064 KB |
Output is correct |
5 |
Correct |
17 ms |
19064 KB |
Output is correct |
6 |
Correct |
17 ms |
19192 KB |
Output is correct |
7 |
Correct |
17 ms |
19192 KB |
Output is correct |
8 |
Correct |
17 ms |
19192 KB |
Output is correct |
9 |
Correct |
17 ms |
19192 KB |
Output is correct |
10 |
Correct |
18 ms |
19192 KB |
Output is correct |
11 |
Correct |
18 ms |
19164 KB |
Output is correct |
12 |
Correct |
18 ms |
19164 KB |
Output is correct |
13 |
Correct |
18 ms |
19192 KB |
Output is correct |
14 |
Correct |
18 ms |
19208 KB |
Output is correct |
15 |
Correct |
18 ms |
19176 KB |
Output is correct |
16 |
Correct |
18 ms |
19196 KB |
Output is correct |
17 |
Correct |
22 ms |
19320 KB |
Output is correct |
18 |
Correct |
19 ms |
19320 KB |
Output is correct |
19 |
Correct |
22 ms |
19324 KB |
Output is correct |
20 |
Correct |
19 ms |
19320 KB |
Output is correct |
21 |
Correct |
19 ms |
19192 KB |
Output is correct |
22 |
Correct |
19 ms |
19320 KB |
Output is correct |
23 |
Correct |
43 ms |
19320 KB |
Output is correct |
24 |
Correct |
21 ms |
19320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19192 KB |
Output is correct |
2 |
Correct |
17 ms |
19192 KB |
Output is correct |
3 |
Correct |
18 ms |
19192 KB |
Output is correct |
4 |
Correct |
17 ms |
19064 KB |
Output is correct |
5 |
Correct |
17 ms |
19064 KB |
Output is correct |
6 |
Correct |
17 ms |
19192 KB |
Output is correct |
7 |
Correct |
17 ms |
19192 KB |
Output is correct |
8 |
Correct |
17 ms |
19192 KB |
Output is correct |
9 |
Correct |
17 ms |
19192 KB |
Output is correct |
10 |
Correct |
18 ms |
19192 KB |
Output is correct |
11 |
Correct |
18 ms |
19164 KB |
Output is correct |
12 |
Correct |
18 ms |
19164 KB |
Output is correct |
13 |
Correct |
18 ms |
19192 KB |
Output is correct |
14 |
Correct |
18 ms |
19208 KB |
Output is correct |
15 |
Correct |
18 ms |
19176 KB |
Output is correct |
16 |
Correct |
18 ms |
19196 KB |
Output is correct |
17 |
Correct |
22 ms |
19320 KB |
Output is correct |
18 |
Correct |
19 ms |
19320 KB |
Output is correct |
19 |
Correct |
22 ms |
19324 KB |
Output is correct |
20 |
Correct |
19 ms |
19320 KB |
Output is correct |
21 |
Correct |
19 ms |
19192 KB |
Output is correct |
22 |
Correct |
19 ms |
19320 KB |
Output is correct |
23 |
Correct |
43 ms |
19320 KB |
Output is correct |
24 |
Correct |
21 ms |
19320 KB |
Output is correct |
25 |
Correct |
44 ms |
20344 KB |
Output is correct |
26 |
Correct |
88 ms |
21876 KB |
Output is correct |
27 |
Correct |
215 ms |
26760 KB |
Output is correct |
28 |
Correct |
209 ms |
30048 KB |
Output is correct |
29 |
Correct |
161 ms |
24808 KB |
Output is correct |
30 |
Correct |
248 ms |
30304 KB |
Output is correct |
31 |
Correct |
331 ms |
30340 KB |
Output is correct |
32 |
Correct |
308 ms |
30180 KB |
Output is correct |
33 |
Correct |
57 ms |
21364 KB |
Output is correct |
34 |
Correct |
164 ms |
24824 KB |
Output is correct |
35 |
Correct |
225 ms |
30176 KB |
Output is correct |
36 |
Correct |
402 ms |
30176 KB |
Output is correct |
37 |
Correct |
367 ms |
30280 KB |
Output is correct |
38 |
Correct |
329 ms |
30176 KB |
Output is correct |