#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const long long inf = (1LL << 60);
int n;
struct Element
{
int pos;
int gold;
int energy;
};
Element a[maxn];
long long prefEenrgy[maxn];
long long prefGold[maxn];
struct SegmentTree
{
struct Node
{
long long maxv;
int pos;
};
Node tree[4 * maxn];
long long lazy[4 * maxn];
Node combine(Node leftChild, Node rightChild)
{
Node result;
if (leftChild.maxv > rightChild.maxv)
{
result = leftChild;
}
else if (rightChild.maxv > leftChild.maxv)
{
result = rightChild;
}
else
{
result.maxv = leftChild.maxv;
result.pos = max(leftChild.pos, rightChild.pos);
}
return result;
}
void build(int node, int l, int r)
{
lazy[node] = 0;
if (l == r)
{
tree[node].maxv = prefEenrgy[l] - a[l].pos;
tree[node].pos = l;
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}
void pushLazy(int node, int l, int r)
{
tree[node].maxv += lazy[node];
if (l != r)
{
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int ql, int qr, long long delta)
{
pushLazy(node, l, r);
if (l > qr || r < ql)
{
return;
}
if (ql <= l && r <= qr)
{
lazy[node] += delta;
pushLazy(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ql, qr, delta);
update(2 * node + 1, mid + 1, r, ql, qr, delta);
tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}
Node query(int node, int l ,int r, int ql, int qr)
{
pushLazy(node, l, r);
if (l > qr || r < ql)
{
return {-inf, -1};
}
if (ql <= l && r <= qr)
{
return tree[node];
}
int mid = (l + r) / 2;
return combine(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr));
}
inline void build()
{
build(1, 1, n);
}
inline void update(int l, int r, long long delta)
{
update(1, 1, n, l, r, delta);
}
inline pair<long long, int> query(int l, int r)
{
Node ans = query(1, 1, n, l, r);
return make_pair(ans.maxv, ans.pos);
}
};
SegmentTree tree;
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i].pos >> a[i].gold >> a[i].energy;
prefEenrgy[i] = prefEenrgy[i - 1] + a[i].energy;
prefGold[i] = prefGold[i - 1] + a[i].gold;
}
for (int i = 2; i <= n; ++i)
{
a[i].pos -= a[1].pos;
}
a[1].pos = 0;
tree.build();
long long ans = -inf;
for (int i = 1; i <= n; ++i)
{
if (prefEenrgy[i] - a[i].pos >= 0)
{
ans = max(ans, prefGold[i]);
}
}
//cout << "now " << ans << endl;
for (int i = 1; i <= n; ++i)
{
if (i == 1)
{
tree.update(i + 1, n, (a[i + 1].pos - a[i].pos) - a[i].energy);
continue;
}
if (a[i].gold >= ans)
{
ans = a[i].gold;
}
int l = i + 1;
int r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (prefGold[mid] - prefGold[i - 1] >= ans)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
int pos = l;
if (pos > n)
{
break;
}
//cout << i << " " << pos << " " << ans << endl;
pair<long long, int> result = tree.query(pos, n);
if (result.first >= 0)
{
ans = max(ans, prefGold[result.second] - prefGold[i - 1]);
}
if (i + 1 <= n)
{
tree.update(i + 1, n, (a[i + 1].pos - a[i].pos) - a[i].energy);
}
}
cout << ans << endl;
return 0;
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
4
1 5 1
2 7 2
5 4 1
8 15 1
2
2 4 1
5 5 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
