#include <bits/stdc++.h>
using namespace std;
class RangeMin {
public:
int size_ = 1;
vector<long long> dat;
void init(int sz) {
while (size_ <= sz) size_ *= 2;
dat.resize(size_ * 2, 0);
}
void update(int pos, long long x) {
pos += size_;
dat[pos] = x;
while (pos >= 2) {
pos >>= 1;
dat[pos] = min(dat[pos * 2], dat[pos * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (r <= a || b <= l) return (1LL << 60);
long long v1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long v2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return min(v1, v2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
long long N, L;
long long A[1 << 19], B[1 << 19], C[1 << 19], D[1 << 19];
long long dpl[1 << 19];
long long dpr[1 << 19];
RangeMin ZL, ZR;
vector<long long> X;
int main() {
// INPUT
cin >> N >> L;
for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];
// ZAATS
for (int i = 0; i < N; i++) X.push_back(A[i]);
for (int i = 0; i < N; i++) X.push_back(B[i]);
for (int i = 0; i < N; i++) X.push_back(C[i]);
X.push_back(1);
X.push_back(L + 1);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
for (int i = 0; i < N; i++) A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();
for (int i = 0; i < N; i++) B[i] = lower_bound(X.begin(), X.end(), B[i] + 1) - X.begin();
for (int i = 0; i < N; i++) C[i] = lower_bound(X.begin(), X.end(), C[i]) - X.begin();
// PRCLC
long long Answer = (1LL << 60);
ZL.init(X.size() + 2);
ZR.init(X.size() + 2);
for (int i = 0; i < (int)X.size(); i++) dpl[i] = (1LL << 60);
for (int i = 0; i < (int)X.size(); i++) dpr[i] = (1LL << 60);
dpl[0] = 0;
dpr[X.size() - 2] = 0;
for (int i = 0; i < (int)X.size(); i++) ZL.update(i, dpl[i]);
for (int i = 0; i < (int)X.size(); i++) ZR.update(i, dpr[i]);
// CALCS
for (int i = 0; i < N; i++) {
long long val1 = ZL.query(A[i], B[i]);
long long val2 = ZR.query(A[i], B[i]);
Answer = min(Answer, val1 + val2 + D[i]);
dpl[C[i]] = min(dpl[C[i]], val1 + D[i]);
dpr[C[i]] = min(dpr[C[i]], val2 + D[i]);
ZL.update(C[i], dpl[C[i]]);
ZR.update(C[i], dpr[C[i]]);
//cout << val1 << " " << val2 << endl;
}
// FINAL
if (Answer == (1LL << 60)) cout << "-1" << endl;
else cout << Answer << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 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 |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 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 |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
360 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 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 |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
360 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
416 KB |
Output is correct |
| 16 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 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 |
512 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
360 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
416 KB |
Output is correct |
| 16 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
