#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define L first
#define R second
using namespace std;
typedef long long lint;
typedef pair<int,int> ii;
const lint inf = 1e17;
struct segment{
lint tree[600005];
int n;
segment(int N){
n = N;
fill(tree, tree+2*n, inf);
}
void update(int i, lint v){
for(i += n;i > 0;i >>= 1) tree[i] = min(tree[i], v);
}
lint query(int l, int r){
lint res = inf;
for(l += n, r += n+1;l < r;l >>= 1, r >>= 1){
if(l&1) res = min(res, tree[l++]);
if(r&1) res = min(res, tree[--r]);
}
return res;
}
} *Left, *Right;
int A[100005], B[100005], C[100005], D[100005];
vector<int> dis;
int get(lint x){
return lower_bound(all(dis), x) - dis.begin();
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, len; cin >> n >> len;
lint ans = inf;
for(int i = 0;i < n;i++){
cin >> A[i] >> B[i] >> C[i] >> D[i];
dis.push_back(A[i]);
dis.push_back(B[i]);
dis.push_back(C[i]);
}
dis.push_back(1);
dis.push_back(len);
sort(all(dis));
dis.erase(unique(all(dis)), dis.end());
Left = new segment(sz(dis)), Right = new segment(sz(dis));
Left->update(get(0), 0); Right->update(get(len), 0);
for(int i = 0;i < n;i++){
int L = get(A[i]), R = get(B[i]), M = get(C[i]), cost = D[i];
lint fromLeft = Left->query(L, R);
lint fromRight = Right->query(L, R);
ans = min(ans, fromLeft + fromRight + cost);
Left->update(M, fromLeft + cost);
Right->update(M, fromRight + cost);
}
if(ans == inf) ans = -1;
cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
488 KB |
Output is correct |
| 17 |
Correct |
2 ms |
512 KB |
Output is correct |
| 18 |
Correct |
1 ms |
512 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Correct |
2 ms |
512 KB |
Output is correct |
| 21 |
Correct |
1 ms |
512 KB |
Output is correct |
| 22 |
Correct |
2 ms |
512 KB |
Output is correct |
| 23 |
Correct |
1 ms |
512 KB |
Output is correct |
| 24 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
512 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
488 KB |
Output is correct |
| 17 |
Correct |
2 ms |
512 KB |
Output is correct |
| 18 |
Correct |
1 ms |
512 KB |
Output is correct |
| 19 |
Correct |
2 ms |
512 KB |
Output is correct |
| 20 |
Correct |
2 ms |
512 KB |
Output is correct |
| 21 |
Correct |
1 ms |
512 KB |
Output is correct |
| 22 |
Correct |
2 ms |
512 KB |
Output is correct |
| 23 |
Correct |
1 ms |
512 KB |
Output is correct |
| 24 |
Correct |
2 ms |
512 KB |
Output is correct |
| 25 |
Correct |
14 ms |
1664 KB |
Output is correct |
| 26 |
Correct |
40 ms |
3700 KB |
Output is correct |
| 27 |
Correct |
120 ms |
6300 KB |
Output is correct |
| 28 |
Correct |
109 ms |
4592 KB |
Output is correct |
| 29 |
Correct |
90 ms |
5368 KB |
Output is correct |
| 30 |
Correct |
148 ms |
4592 KB |
Output is correct |
| 31 |
Correct |
211 ms |
9064 KB |
Output is correct |
| 32 |
Correct |
182 ms |
7660 KB |
Output is correct |
| 33 |
Correct |
22 ms |
3584 KB |
Output is correct |
| 34 |
Correct |
93 ms |
7164 KB |
Output is correct |
| 35 |
Correct |
117 ms |
16488 KB |
Output is correct |
| 36 |
Correct |
237 ms |
16492 KB |
Output is correct |
| 37 |
Correct |
193 ms |
16648 KB |
Output is correct |
| 38 |
Correct |
163 ms |
16488 KB |
Output is correct |
