/*
__
/\ \
_ __ ___ ___\ \ \/'\ ___ __ ___ ___ __
/\`'__\/ __`\ /'___\ \ , < / __`\ /'__`\ /' _ `\ /' _ `\ /'__`\
\ \ \//\ \L\ \/\ \__/\ \ \\`\ /\ \L\ \/\ \L\.\_/\ \/\ \/\ \/\ \/\ \L\.\_
\ \_\\ \____/\ \____\\ \_\ \_\ \____/\ \__/.\_\ \_\ \_\ \_\ \_\ \__/.\_\
\/_/ \/___/ \/____/ \/_/\/_/\/___/ \/__/\/_/\/_/\/_/\/_/\/_/\/__/\/_/
*/
#ifndef __AHA__HEADER
#define __AHA__HEADER
#include <bits/stdc++.h>
using namespace std;
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
#define ft first
#define sd second
#define sz(x) (i6) x.size()
#define psb(x) push_back(x)
#define ppb() pop_back()
#define bg(x) x.begin()
#define ed(x) x.end()
#define col(x) x.begin(), x.end()
#define srt(x) sort(x.begin(), x.end())
#define pq priority_queue
#define fn function
#ifdef LOCAL
#define git stauDBG_MACRO_NO_WARNING
#include <dbg.h>
#else
#define dbg(...)
#endif
#define endl '\n'
template <typename T>
using vec = vector<T>;
template <typename T>
using deq = deque<T>;
template <typename K, typename V>
using hmap = unordered_map<K, V>;
using str = string;
using vb = vec<bool>;
using byte = int8_t;
using i3 = int32_t;
using i6 = int64_t;
using i64 = int64_t;
using u3 = uint32_t;
using u6 = uint64_t;
using d6 = long double;
using p3 = pair<i3, i3>;
using vi3 = vec<i3>;
using vp3 = vec<p3>;
using p6 = pair<i6, i6>;
using vi6 = vec<i6>;
using vd6 = vec<d6>;
using vp6 = vec<p6>;
using vv = vec<vi6>;
using dp6 = deq<p6>;
using di6 = deq<i6>;
using mi6 = map<i6, i6>;
using mp6 = map<p6, i6>;
using si6 = set<i6>;
using hi6 = hmap<i6, i6>;
using bs = bitset<64>;
using graph = vv;
using matrix = vv;
const d6 EPS = 1 / 1000000.0;
const i6 ZERO = 0;
const i6 _0 = ZERO;
const i6 ONE = 1;
const i6 _1 = ONE;
const i6 INF = INT64_MAX / 4;
const i6 NINF = -INF;
namespace std {
template <typename T1, typename T2>
struct hash<pair<T1, T2>> {
std::size_t operator()(const pair<T1, T2>& pair) const noexcept {
return hash<T1>()(pair.first) ^ hash<T2>()(pair.second);
}
};
} // namespace std
template <typename T1, typename T2>
istream& operator>>(istream& stream, pair<T1, T2>& p) {
stream >> p.ft;
stream >> p.sd;
return stream;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
return stream << p.ft << " " << p.sd;
}
template <typename T>
istream& operator>>(istream& stream, vec<T>& v) {
if (v.empty()) {
u6 len;
stream >> len;
v.assign(len, T());
}
for (auto i = 0; i < sz(v); i++) {
stream >> v[i];
}
return stream;
}
template <typename T>
ostream& operator<<(ostream& stream, const vec<T>& v) {
if (!v.empty()) {
stream << v[0];
}
for (auto i = 1; i < sz(v); i++) {
stream << " " << v[i];
}
return stream;
}
template <typename T>
istream& operator>>(istream& stream, deq<T>& v) {
if (v.empty()) {
u6 len;
stream >> len;
v.assign(len, T());
}
for (auto i = 0; i < sz(v); i++) {
stream >> v[i];
}
return stream;
}
template <typename T>
ostream& operator<<(ostream& stream, const deq<T>& v) {
if (!v.empty()) {
stream << v[0];
}
for (auto i = 1; i < sz(v); i++) {
stream << " " << v[i];
}
return stream;
}
#endif
class segtree {
private:
vector<i64> data;
public:
segtree(i64 len) { data.assign(4 * len, INF); }
void update(i64 crt, i64 s, i64 d, i64 val, i64 pos) {
if (s == d) {
data[crt] = val;
return;
}
i64 mid = (s + d) / 2;
if (pos <= mid) {
update(crt * 2, s, mid, val, pos);
} else {
update(crt * 2 + 1, mid + 1, d, val, pos);
}
data[crt] = min(data[crt * 2], data[crt * 2 + 1]);
}
i64 b_search(i64 crt, i64 s, i64 d, i64 val) {
if (s == d) {
return s;
}
if (data[2 * crt] <= val) {
return b_search(2 * crt, s, (s + d) / 2, val);
} else {
return b_search(2 * crt + 1, (s + d) / 2 + 1, d, val);
}
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
ifstream cin{"input.txt"};
ofstream cout{"output.txt"};
#endif
i64 n;
cin >> n;
vector<i64> pos(n);
vector<i64> sg(n);
vector<i64> se(n);
for (i64 i = 0; i < n; i++) {
i64 x, g, e;
cin >> x >> g >> e;
pos[i] = x;
sg[i] += g;
se[i] += e;
if (i != 0) {
sg[i] += sg[i - 1];
se[i] += se[i - 1];
}
}
segtree st(n);
i64 res = 0;
for (i64 i = 0; i < n; i++) {
if (i == 0) {
st.update(1, 0, n - 1, -pos[i], i);
} else {
st.update(1, 0, n - 1, se[i - 1] - pos[i], i);
}
i64 s = st.b_search(1, 0, n - 1, se[i] - pos[i]);
if (s == 0) {
res = max(res, sg[i]);
} else {
res = max(res, sg[i] - sg[s - 1]);
}
}
cout << res;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
316 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
316 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
332 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 |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
3 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
316 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
316 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
332 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 |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
340 KB |
Output is correct |
23 |
Correct |
3 ms |
588 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
2 ms |
596 KB |
Output is correct |
26 |
Correct |
3 ms |
980 KB |
Output is correct |
27 |
Correct |
4 ms |
1052 KB |
Output is correct |
28 |
Correct |
18 ms |
4056 KB |
Output is correct |
29 |
Correct |
20 ms |
4316 KB |
Output is correct |
30 |
Correct |
52 ms |
8672 KB |
Output is correct |
31 |
Correct |
35 ms |
7488 KB |
Output is correct |
32 |
Correct |
38 ms |
7628 KB |
Output is correct |
33 |
Correct |
45 ms |
7380 KB |
Output is correct |
34 |
Correct |
38 ms |
7372 KB |
Output is correct |
35 |
Correct |
38 ms |
7884 KB |
Output is correct |
36 |
Correct |
41 ms |
8012 KB |
Output is correct |