#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
struct segtree {
vector<long long> st;
int sz;
segtree(vector<long long> a) {
sz = a.size();
while (sz & sz - 1) ++sz;
st.resize(sz << 1, INF);
for (int i = 0; i < a.size(); i++) st[i + sz] = a[i];
for (int i = sz - 1; i; --i) pull(i);
}
void pull(int v) {
st[v] = min(st[v << 1], st[v << 1 | 1]);
}
int findfirst(int v, int l, int r, int ql, int qr, long long x) {
if (l > qr || r < ql) return -1;
if (l >= ql && r <= qr) {
if (st[v] > x) return -1;
while (l < r) {
int m = l + r >> 1;
if (st[v << 1] <= x) v <<= 1, r = m;
else v <<= 1, v |= 1, l = m + 1;
}
return l;
}
int m = l + r >> 1;
int s = findfirst(v << 1, l, m, ql, qr, x);
if (s != -1) return s;
return findfirst(v << 1 | 1, m + 1, r, ql, qr, x);
}
int findfirst(int l, int r, long long x) {
return findfirst(1, 0, sz - 1, l, r, x);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> x(n), g(n), d(n);
for (int i = 0; i < n; i++) cin >> x[i] >> g[i] >> d[i];
vector<long long> pre1(n + 1), pre2(n + 1), f(n + 1);
for (int i = 0; i < n; i++) pre1[i + 1] = pre1[i] + g[i], pre2[i + 1] = pre2[i] + d[i];
f[0] = INF;
for (int i = 1; i <= n; i++) f[i] = pre2[i - 1] - x[i - 1];
segtree st(f);
long long ans = -INF;
for (int i = 1; i <= n; i++) {
int k = st.findfirst(0, i, pre2[i] - x[i - 1]);
if (k == -1) continue;
ans = max(ans, pre1[i] - pre1[k - 1]);
}
cout << ans << '\n';
}
Compilation message
divide.cpp: In constructor 'segtree::segtree(std::vector<long long int>)':
divide.cpp:11:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
11 | while (sz & sz - 1) ++sz;
| ~~~^~~
divide.cpp:13:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i = 0; i < a.size(); i++) st[i + sz] = a[i];
| ~~^~~~~~~~~~
divide.cpp: In member function 'int segtree::findfirst(int, int, int, int, int, long long int)':
divide.cpp:24:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int m = l + r >> 1;
| ~~^~~
divide.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int m = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
464 KB |
Output is correct |
23 |
Correct |
2 ms |
724 KB |
Output is correct |
24 |
Correct |
2 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
324 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
464 KB |
Output is correct |
23 |
Correct |
2 ms |
724 KB |
Output is correct |
24 |
Correct |
2 ms |
760 KB |
Output is correct |
25 |
Correct |
2 ms |
720 KB |
Output is correct |
26 |
Correct |
3 ms |
1108 KB |
Output is correct |
27 |
Correct |
3 ms |
1108 KB |
Output is correct |
28 |
Correct |
17 ms |
4436 KB |
Output is correct |
29 |
Correct |
16 ms |
4820 KB |
Output is correct |
30 |
Correct |
37 ms |
9540 KB |
Output is correct |
31 |
Correct |
30 ms |
8396 KB |
Output is correct |
32 |
Correct |
30 ms |
8404 KB |
Output is correct |
33 |
Correct |
28 ms |
8272 KB |
Output is correct |
34 |
Correct |
36 ms |
8276 KB |
Output is correct |
35 |
Correct |
38 ms |
8784 KB |
Output is correct |
36 |
Correct |
38 ms |
8916 KB |
Output is correct |