#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const int N = 1e5+5;
struct interval {
int l, r, pos, cost;
};
//-------------------------------
interval a[N];
int n, len;
vector<int> vals;
struct SegmentTree {
ll seg[N*8];
SegmentTree() {
memset(seg, 0x3f, sizeof(seg));
}
void update(int pos, ll val, int l = 0, int r = vals.size() - 1, int id = 1) {
if (l > pos || r < pos) return;
if (l == r) {
seg[id] = min(seg[id], val);
return;
}
int mid = (l+r) / 2;
update(pos, val, l, mid, id*2);
update(pos, val, mid+1, r, id*2 + 1);
seg[id] = min(seg[id*2], seg[id*2 + 1]);
}
ll get(int u, int v, int l = 0, int r = vals.size() - 1, int id = 1) {
if (l > v || r < u) return 4e18;
if (l >= u && r <= v) return seg[id];
int mid = (l+r) / 2;
return min(get(u, v, l, mid, id*2),
get(u, v, mid+1, r, id*2 + 1));
}
} lTree, rTree;
int idx(int val) {
return lower_bound(vals.begin(), vals.end(), val) - vals.begin();
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> len;
for (int i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r >> a[i].pos >> a[i].cost;
vals.push_back(a[i].l);
vals.push_back(a[i].r);
}
vals.push_back(0); vals.push_back(len+1);
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
for (int i = 1; i <= n; i++) {
a[i].l = idx(a[i].l); a[i].r = idx(a[i].r); a[i].pos = idx(a[i].pos);
}
ll ans = 4e18;
lTree.update(idx(1), 0); rTree.update(idx(n), 0);
for (int i = 1; i <= n; i++) {
ll v1 = lTree.get(a[i].l, a[i].r) + a[i].cost;
ll v2 = rTree.get(a[i].l, a[i].r) + a[i].cost;
ans = min(ans, v1+v2 - a[i].cost);
lTree.update(a[i].pos, v1);
rTree.update(a[i].pos, v2);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
