#include <bits/stdc++.h>
using namespace std;
template<typename S, S (*op)(S, S), S (*e)()> struct dynamic_segtree {
public:
dynamic_segtree() : left(nullptr), right(nullptr) {}
dynamic_segtree(int64_t _lt, int64_t _rt, S _val = e()) :
lt_idx(_lt), rt_idx(_rt), mid_idx((_lt + _rt) >> 1), val(_val) {
if (_lt != _rt) {
left = new dynamic_segtree<S, op, e>(_lt, mid_idx);
right = new dynamic_segtree<S, op, e>(mid_idx + 1, _rt);
}
}
void update(int64_t p, S new_val) {
if (lt_idx == rt_idx) return void(val = op(val, new_val));
if (p <= mid_idx) left->update(p, new_val);
else right->update(p, new_val);
val = op(left->val, right->val);
}
S prod(int64_t ql, int64_t qr) {
if (qr < lt_idx || rt_idx < ql) return e();
if (ql <= lt_idx && rt_idx <= qr) return val;
auto left_val = left->prod(ql, qr);
auto right_val = right->prod(ql, qr);
return op(left_val, right_val);
}
private:
dynamic_segtree<S, op, e> *left, *right;
int64_t lt_idx, rt_idx, mid_idx;
S val;
};
int64_t op(int64_t a, int64_t b) { return min(a, b); }
int64_t e() { return int64_t(1e18); }
const int N = 1e5 + 2;
int m, n, a[N], b[N], c[N], d[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> m >> n;
for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];
vector<int> compr({1, n}); compr.reserve(n * 3 + 2);
for (int i = 0; i < m; i++)
compr.push_back(a[i]), compr.push_back(b[i]), compr.push_back(c[i]);
sort(compr.begin(), compr.end());
compr.erase(unique(compr.begin(), compr.end()), compr.end());
auto get_compress_value = [&compr](int x) {
return lower_bound(compr.begin(), compr.end(), x) - compr.begin() + 1;
};
n = get_compress_value(n);
for (int i = 0; i < m; i++) {
a[i] = get_compress_value(a[i]);
b[i] = get_compress_value(b[i]);
c[i] = get_compress_value(c[i]);
}
auto *Ltree = new dynamic_segtree<int64_t, op, e>(1, n);
auto *Rtree = new dynamic_segtree<int64_t, op, e>(1, n);
Ltree->update(1, 0), Rtree->update(n, 0);
int64_t ans = e();
for (int i = 0; i < m; i++) {
auto min_val_left = Ltree->prod(a[i], b[i]);
auto min_val_right = Rtree->prod(a[i], b[i]);
ans = min(ans, min_val_left + min_val_right + d[i]);
Ltree->update(c[i], d[i] + min_val_left);
Rtree->update(c[i], d[i] + min_val_right);
}
cout << (ans == e() ? -1 : ans) << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
328 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
328 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
328 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
328 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
1 ms |
468 KB |
Output is correct |
| 14 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 15 |
Halted |
0 ms |
0 KB |
- |
