#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;
map<int, int> cc;
struct SegTree {
vector<ll> st;
int n;
void init(int _n) {
n = _n; st.assign(2*n, inf);
}
void upd(int p, ll v) {
p += n;
st[p] = min(st[p], v);
for (p /= 2; p; p /= 2) st[p] = min(st[2*p], st[2*p+1]);
}
ll qry(int l, int r) {
ll a = inf;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) a = min(a, st[l++]);
if (r&1) a = min(a, st[--r]);
}
return a;
}
} lft, rht;
int main() {
int m, n; cin >> m >> n;
int L[m], R[m], T[m], C[m];
for (int i = 0; i < m; i++) cin >> L[i] >> R[i] >> T[i] >> C[i];
vector<int> pts;
for (int i = 0; i < m; i++) {
pts.push_back(L[i]);
pts.push_back(R[i]);
pts.push_back(T[i]);
}
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
int np = pts.size();
lft.init(np); rht.init(np);
for (int i = 0; i < np; i++) {
cc[pts[i]] = i;
}
ll dpLeft[m], dpRight[m];
for (int i = 0; i < m; i++) {
dpLeft[i] = dpRight[i] = inf;
if (L[i] == 1) dpLeft[i] = C[i];
if (R[i] == n) dpRight[i] = C[i];
dpLeft[i] = min(dpLeft[i], C[i] + lft.qry(cc[L[i]], cc[R[i]]));
dpRight[i] = min(dpRight[i], C[i] + rht.qry(cc[L[i]], cc[R[i]]));
lft.upd(cc[T[i]], dpLeft[i]);
rht.upd(cc[T[i]], dpRight[i]);
}
ll opt = inf;
for (int i = 0; i < m; i++) {
opt = min(opt, dpLeft[i] + dpRight[i] - C[i]);
}
if (opt == inf) cout << -1 << endl;
else cout << opt << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
128 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
128 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
128 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
256 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
8 ms |
512 KB |
Output is correct |
| 18 |
Correct |
7 ms |
384 KB |
Output is correct |
| 19 |
Correct |
8 ms |
512 KB |
Output is correct |
| 20 |
Correct |
8 ms |
512 KB |
Output is correct |
| 21 |
Correct |
6 ms |
512 KB |
Output is correct |
| 22 |
Correct |
8 ms |
640 KB |
Output is correct |
| 23 |
Correct |
8 ms |
640 KB |
Output is correct |
| 24 |
Correct |
8 ms |
640 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
4 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
256 KB |
Output is correct |
| 6 |
Correct |
4 ms |
128 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
256 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
256 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
8 ms |
512 KB |
Output is correct |
| 18 |
Correct |
7 ms |
384 KB |
Output is correct |
| 19 |
Correct |
8 ms |
512 KB |
Output is correct |
| 20 |
Correct |
8 ms |
512 KB |
Output is correct |
| 21 |
Correct |
6 ms |
512 KB |
Output is correct |
| 22 |
Correct |
8 ms |
640 KB |
Output is correct |
| 23 |
Correct |
8 ms |
640 KB |
Output is correct |
| 24 |
Correct |
8 ms |
640 KB |
Output is correct |
| 25 |
Correct |
40 ms |
2040 KB |
Output is correct |
| 26 |
Correct |
118 ms |
5744 KB |
Output is correct |
| 27 |
Correct |
360 ms |
13804 KB |
Output is correct |
| 28 |
Correct |
319 ms |
8652 KB |
Output is correct |
| 29 |
Correct |
270 ms |
11628 KB |
Output is correct |
| 30 |
Correct |
390 ms |
9956 KB |
Output is correct |
| 31 |
Correct |
595 ms |
21604 KB |
Output is correct |
| 32 |
Correct |
539 ms |
18020 KB |
Output is correct |
| 33 |
Correct |
80 ms |
6516 KB |
Output is correct |
| 34 |
Correct |
302 ms |
16108 KB |
Output is correct |
| 35 |
Correct |
449 ms |
31972 KB |
Output is correct |
| 36 |
Correct |
727 ms |
32228 KB |
Output is correct |
| 37 |
Correct |
613 ms |
32100 KB |
Output is correct |
| 38 |
Correct |
569 ms |
32100 KB |
Output is correct |
