#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll, ll> tpl;
const ll MXN = 3e5 + 10;
const ll MXS = MXN * 2;
const ll INF = 1e18;
ll n, m, k, ans;
ll A[MXN], B[MXN], C[MXN], D[MXN];
vector<ll> Num;
inline int GetId(ll x){
return lower_bound(Num.begin(), Num.end(), x) - Num.begin() + 1;
}
struct Segtree {
ll seg[MXS], lim;//lim as size
void init(){
lim = k + 1;
for(int i = lim << 1; -- i; ) seg[i] = INF;
}
void Upd(ll p, ll x){
p += lim;
while(p) seg[p] = min(seg[p], x), p >>= 1;
}
ll Get(ll l, ll r){
ll res = INF; l += lim, r += lim;
while(l <= r){
if((l & 1) == 1) res = min(res, seg[l]), l ++;
if((r & 1) == 0) res = min(res, seg[r]), r --;
l >>= 1, r >>= 1;
}
return res;
}
} SL, SR;
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n >> m, ans = INF;
for(int i = 1; i <= n; i ++){
cin >> A[i] >> B[i] >> C[i] >> D[i];
Num.push_back(A[i]), Num.push_back(B[i]), Num.push_back(C[i]);
}
Num.push_back(1), Num.push_back(m);
sort(Num.begin(), Num.end());
Num.resize(k = unique(Num.begin(), Num.end()) - Num.begin());
SL.init(), SR.init();
SL.Upd(1, 0), SR.Upd(k, 0);
for(int i = 1; i <= n; i ++){
A[i] = GetId(A[i]), B[i] = GetId(B[i]), C[i] = GetId(C[i]);
ll cl = SL.Get(A[i], B[i]), cr = SR.Get(A[i], B[i]);
ans = min(ans, cl + cr + D[i]);
cl += D[i], cr += D[i];
SL.Upd(C[i], cl), SR.Upd(C[i], cr);
}
cout << (ans == INF ? -1 : ans) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
324 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
324 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
324 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
2 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
460 KB |
Output is correct |
| 21 |
Correct |
1 ms |
460 KB |
Output is correct |
| 22 |
Correct |
2 ms |
588 KB |
Output is correct |
| 23 |
Correct |
1 ms |
588 KB |
Output is correct |
| 24 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
0 ms |
324 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
320 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
2 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
460 KB |
Output is correct |
| 21 |
Correct |
1 ms |
460 KB |
Output is correct |
| 22 |
Correct |
2 ms |
588 KB |
Output is correct |
| 23 |
Correct |
1 ms |
588 KB |
Output is correct |
| 24 |
Correct |
2 ms |
588 KB |
Output is correct |
| 25 |
Correct |
14 ms |
1844 KB |
Output is correct |
| 26 |
Correct |
39 ms |
4440 KB |
Output is correct |
| 27 |
Correct |
118 ms |
9888 KB |
Output is correct |
| 28 |
Correct |
114 ms |
10808 KB |
Output is correct |
| 29 |
Correct |
86 ms |
7968 KB |
Output is correct |
| 30 |
Correct |
143 ms |
10860 KB |
Output is correct |
| 31 |
Correct |
183 ms |
15088 KB |
Output is correct |
| 32 |
Correct |
177 ms |
13596 KB |
Output is correct |
| 33 |
Correct |
23 ms |
4044 KB |
Output is correct |
| 34 |
Correct |
79 ms |
9808 KB |
Output is correct |
| 35 |
Correct |
116 ms |
19120 KB |
Output is correct |
| 36 |
Correct |
219 ms |
19120 KB |
Output is correct |
| 37 |
Correct |
166 ms |
19116 KB |
Output is correct |
| 38 |
Correct |
171 ms |
19096 KB |
Output is correct |
