#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define lb(x...) lower_bound(x)
#define ff first
#define ss second
using ll = int64_t;
template<class T> bool ckmin(T &a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 1 << 17;
const int inf = 1e9;
int t[N << 1];
int n;
int query(int l, int r) {
int res = inf;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ckmin(res, t[l++]);
if (r & 1) ckmin(res, t[--r]);
}
return res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
vector<ll> x(n), g(n + 1), e(n + 1), diff(n);
rep(i, 0, n) {
cin >> x[i] >> g[i + 1] >> e[i + 1];
g[i + 1] += g[i];
e[i + 1] += e[i];
diff[i] = x[i] - e[i];
}
rep(i, 0, n) t[i + n] = i;
sort(t + n, t + 2 * n, [&](int a, int b) { return diff[a] < diff[b]; });
for (int i = n - 1; i; --i) t[i] = min(t[i << 1|0], t[i << 1|1]);
sort(all(diff));
ll ans = 0;
rep(i, 0, n) {
// Find smallest j such that x[j] - e[j] >= x[i] - e[i + 1]
int k = lb(all(diff), x[i] - e[i + 1]) - begin(diff);
// [k, n) are the elements such that diff[k] >= x[i] - e[i + 1]
// find smallest j in [k, n) in segtree
int j = query(k, n);
ckmax(ans, g[i + 1] - g[j]);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
7 ms |
512 KB |
Output is correct |
| 24 |
Correct |
7 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
4 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
7 ms |
512 KB |
Output is correct |
| 24 |
Correct |
7 ms |
512 KB |
Output is correct |
| 25 |
Correct |
7 ms |
512 KB |
Output is correct |
| 26 |
Correct |
9 ms |
768 KB |
Output is correct |
| 27 |
Correct |
9 ms |
768 KB |
Output is correct |
| 28 |
Correct |
31 ms |
2304 KB |
Output is correct |
| 29 |
Correct |
32 ms |
2304 KB |
Output is correct |
| 30 |
Correct |
63 ms |
4320 KB |
Output is correct |
| 31 |
Correct |
55 ms |
4224 KB |
Output is correct |
| 32 |
Correct |
55 ms |
4216 KB |
Output is correct |
| 33 |
Correct |
54 ms |
4216 KB |
Output is correct |
| 34 |
Correct |
57 ms |
4344 KB |
Output is correct |
| 35 |
Correct |
63 ms |
6648 KB |
Output is correct |
| 36 |
Correct |
63 ms |
6648 KB |
Output is correct |
