#include <bits/stdc++.h>
using namespace std;
struct Seg {
int n;
vector<long long> mn, lazy;
Seg(int n=0): n(n), mn(4*n,0), lazy(4*n,0) {}
void push(int p) {
if (lazy[p]==0) return;
for (int c : {p<<1, (p<<1)|1}) {
mn[c] += lazy[p];
lazy[c] += lazy[p];
}
lazy[p] = 0;
}
void build(int p, int l, int r, const vector<long long>& base) {
if (l == r) {
mn[p] = base[l];
return;
}
int m = (l+r)>>1;
build(p<<1, l, m, base);
build(p<<1|1, m+1, r, base);
mn[p] = min(mn[p<<1], mn[p<<1|1]);
}
void add(int p, int l, int r, int ql, int qr, long long v) {
if (ql>r || qr<l) return;
if (ql<=l && r<=qr) {
mn[p] += v;
lazy[p] += v;
return;
}
push(p);
int m = (l+r)>>1;
add(p<<1, l, m, ql, qr, v);
add(p<<1|1, m+1, r, ql, qr, v);
mn[p] = min(mn[p<<1], mn[p<<1|1]);
}
long long getMin() { return mn[1]; }
};
struct Station {
int x;
long long a, b;
int ix;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long D;
cin >> N >> D;
vector<Station> st(N);
for (int i=0; i<N; i++) cin >> st[i].x >> st[i].a >> st[i].b;
st.push_back({(int)D, 0, D, 0});
int M = N+1;
sort(st.begin(), st.end(), [](auto &u, auto &v){ return u.x < v.x; });
for (int i=0; i<M; i++) st[i].ix = i;
vector<int> ord(M);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i,int j){
if (st[i].b != st[j].b) return st[i].b < st[j].b;
return st[i].x < st[j].x;
});
vector<long long> uniqB;
for (int id : ord) {
if (uniqB.empty() || uniqB.back() != st[id].b)
uniqB.push_back(st[id].b);
}
long long F = uniqB[0];
vector<long long> base(M);
for (int i=0; i<M; i++) base[i] = F - st[i].x;
Seg seg(M);
seg.build(1, 0, M-1, base);
for (int i=0; i<M; i++) {
if (i+1 <= M-1 && st[i].a)
seg.add(1, 0, M-1, i+1, M-1, st[i].a);
}
int ptr = 0;
while (ptr<M && st[ord[ptr]].b == F) ++ptr;
if (seg.getMin() >= 0) {
cout << F - seg.getMin() << "\n";
return 0;
}
int last_cut = 0;
for (size_t t=1; t<uniqB.size(); t++) {
long long nextF = uniqB[t];
long long delta = nextF - F;
seg.add(1, 0, M-1, 0, M-1, delta);
for (int k=last_cut; k<ptr; k++) {
int i = ord[k], L = st[i].ix + 1;
if (L <= M-1 && st[i].a)
seg.add(1, 0, M-1, L, M-1, -st[i].a);
}
last_cut = ptr;
while (ptr<M && st[ord[ptr]].b == nextF) ++ptr;
F = nextF;
if (seg.getMin() >= 0) {
cout << F - seg.getMin() << "\n";
return 0;
}
}
cout << F - seg.getMin() << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |