#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int INF = 1e16;
struct SegmentTree{
vector<int> a; int sz = 1;
SegmentTree(int n){
while(sz < n) sz += sz;
a.assign(2*sz, INF);
}
void update(int i, int v, int x, int lx, int rx){
if(rx-lx==1) return void(a[x] = min(a[x], v));
int mx = (lx + rx) / 2;
if(i < mx) update(i, v, 2*x+1, lx, mx);
else update(i, v, 2*x+2, mx, rx);
a[x] = min(a[2*x+1], a[2*x+2]);
}
void update(int i, int v){ update(i, v, 0, 0, sz); }
int rangeMin(int l, int r, int x, int lx, int rx){
if(r<=lx || rx<=l) return INF;
if(l<=lx && rx<=r) return a[x];
int mx = (lx + rx) / 2;
return min(rangeMin(l, r, 2*x+1, lx, mx), rangeMin(l, r, 2*x+2, mx, rx));
}
int rangeMin(int l, int r){ return rangeMin(l, r+1, 0, 0, sz); }
};
signed main(){
cin.tie(0)->sync_with_stdio(0);
int m, n; cin >> m >> n;
array<int, 4> a[m];
vector<int> vals = {1, n};
for(auto &i : a){
for(int j=0; j<3; ++j) cin >> i[j], vals.push_back(i[j]);
cin >> i[3];
}
sort(vals.begin(), vals.end());
for(auto &i : a){
for(int j=0; j<3; ++j) i[j] = lower_bound(vals.begin(), vals.end(), i[j]) - vals.begin();
}
int last = lower_bound(vals.begin(), vals.end(), n) - vals.begin();
SegmentTree dpL(last+1), dpR(last+1);
dpL.update(0, 0);
dpR.update(last, 0);
int res = INF;
for(auto &i : a){
int l = dpL.rangeMin(i[0], i[2]);
int r = dpR.rangeMin(i[2], i[1]);
res = min(res, l + r + i[3]);
dpL.update(i[2], l + i[3]);
dpR.update(i[2], r + i[3]);
}
cout << (res == INF ? -1 : res);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
