// https://oj.uz/problem/view/JOI19_dishes
#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e18;
class segtree_t {
public:
segtree_t *left, *right;
int l, r, m;
int64_t val, lazy_add, lazy_max;
segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy_add(0), lazy_max(-inf) {
if (l == r) return;
left = new segtree_t(l, m);
right = new segtree_t(m + 1, r);
}
void update_add(int s, int t, int64_t x) {
if (l > t || r < s) return;
if (s <= l && r <= t) {
val += x;
lazy_add += x;
lazy_max += x;
return;
}
Down();
left->update_add(s, t, x);
right->update_add(s, t, x);
Up();
}
void update_max(int s, int t, int64_t x) {
if (l > t || r < s) return;
if (s <= l && r <= t) {
val = max(val, x);
lazy_max = max(lazy_max, x);
return;
}
Down();
left->update_max(s, t, x);
right->update_max(s, t, x);
Up();
}
int64_t get(int s, int t) {
if (l > t || r < s) return -inf;
if (s <= l && r <= t) return val;
Down();
return max(left->get(s, t), right->get(s, t));
}
void Down() {
left->lazy_add += lazy_add;
right->lazy_add += lazy_add;
left->val += lazy_add;
right->val += lazy_add;
left->val = max(left->val, lazy_max);
right->val = max(right->val, lazy_max);
left->lazy_max = max(left->lazy_max, lazy_max);
right->lazy_max = max(right->lazy_max, lazy_max);
lazy_add = 0;
lazy_max = -inf;
}
void Up() {
val = max(left->val, right->val);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int64_t> a(n + 1), s(n), p(n);
vector<int64_t> b(m + 1), t(m), q(m);
for (int i = 0; i < n; i++) cin >> a[i + 1] >> s[i] >> p[i];
for (int i = 0; i < m; i++) cin >> b[i + 1] >> t[i] >> q[i];
for (int i = 0; i < n; i++) a[i + 1] += a[i];
for (int i = 0; i < m; i++) b[i + 1] += b[i];
for (int i = 0; i < n; i++) s[i] -= a[i + 1];
for (int i = 0; i < m; i++) t[i] -= b[i + 1];
vector<int> c(n), d(m);
for (int i = 0; i < n; i++) c[i] = upper_bound(b.begin(), b.end(), s[i]) - b.begin() - 1;
for (int i = 0; i < m; i++) d[i] = upper_bound(a.begin(), a.end(), t[i]) - a.begin() - 1;
segtree_t *dp = new segtree_t(0, m);
vector<vector<pair<int, int>>> upd(n);
for (int i = 0; i < m; i++) {
if (d[i] == 0) dp->update_add(i + 1, m, q[i]);
if (d[i] > 0) upd[d[i] - 1].emplace_back(i + 1, q[i]);
}
for (int i = 0; i < n; i++) {
sort(upd[i].begin(), upd[i].end());
upd[i].emplace_back(m + 1, -1);
if (c[i] != -1) dp->update_add(0, c[i], p[i]);
int64_t sum = 0;
dp->update_max(c[i] + 1, upd[i][0].first - 1, dp->get(0, c[i]));
int last = 0;
for (int j = 0; j + 1 < upd[i].size(); j++) {
sum += upd[i][j].second;
int64_t x = dp->get(last, upd[i][j].first - 1);
dp->update_add(upd[i][j].first, upd[i][j + 1].first - 1, sum);
dp->update_max(upd[i][j].first, upd[i][j + 1].first - 1, x + upd[i][j].second);
last = upd[i][j].first;
}
}
cout << dp->get(m, m);
}
Compilation message
dishes.cpp: In constructor 'segtree_t::segtree_t(int, int)':
dishes.cpp:14:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
14 | segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1), val(0), lazy_add(0), lazy_max(-inf) {
| ~~^~~
dishes.cpp: In function 'int32_t main()':
dishes.cpp:103:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int j = 0; j + 1 < upd[i].size(); j++) {
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
48100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
756 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
756 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
756 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
756 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
756 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
48100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
314 ms |
48100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
