#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e6 + 10;
int n, m;
ll a[maxn], s[maxn], p[maxn];
ll b[maxn], t[maxn], q[maxn];
ll pref[2][maxn];
void input()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> a[i] >> s[i] >> p[i];
for (int i = 1; i <= m; i ++)
cin >> b[i] >> t[i] >> q[i];
}
void prefix_sums()
{
for (int i = 1; i <= n; i ++)
{
pref[0][i] = pref[0][i - 1] + a[i];
}
for (int i = 1; i <= m; i ++)
{
pref[1][i] = pref[1][i - 1] + b[i];
}
}
ll dp[maxn], temp[maxn];
vector < pair < int, ll > > upd[maxn];
int X[maxn], Y[maxn];
const ll inf = 1e18;
ll tree[4 * maxn];
pair < ll, ll > lazy[4 * maxn]; /// first is addition; second is set
pair < int, int > tag[4 * maxn];
void push_lazy(int root, int left, int right)
{
if (tag[root].second == 1)
{
tree[root] = lazy[root].second;
}
if (tag[root].first == 1)
tree[root] += lazy[root].first;
if (left != right)
{
if (tag[root].second == 1)
{
lazy[root * 2] = {0, lazy[root].second};
lazy[root * 2 + 1] = {0, lazy[root].second};
tag[root * 2] = {0, 1};
tag[root * 2 + 1] = {0, 1};
}
if (tag[root].first == 1)
{
lazy[root * 2].first += lazy[root].first;
lazy[root * 2 + 1].first += lazy[root].first;
tag[root * 2].first = 1;
tag[root * 2 + 1].first = 1;
}
}
lazy[root] = {0, 0};
tag[root] = {0, 0};
}
void build(int root, int left, int right)
{
if (left == right)
{
tree[root] = dp[left];
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
ll query(int root, int left, int right, int pivot)
{
push_lazy(root, left, right);
if (left == right)
return tree[root];
int mid = (left + right) / 2;
if (pivot <= mid)
return query(root * 2, left, mid, pivot);
else
return query(root * 2 + 1, mid + 1, right, pivot);
}
void range_add(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = {val, 0};
tag[root] = {1, 0};
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
range_add(root * 2, left, mid, qleft, qright, val);
range_add(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
void set_range(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root] = {0, val};
tag[root] = {0, 1};
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
set_range(root * 2, left, mid, qleft, qright, val);
set_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
int walk(int root, int left, int right, int qleft, int qright, ll val)
{
push_lazy(root, left, right);
if (left > qright || right < qleft || tree[root] >= val)
return qleft - 1;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (tree[root * 2 + 1] < val)
return walk(root * 2 + 1, mid + 1, right, qleft, qright, val);
return walk(root * 2, left, mid, qleft, qright, val);
}
return max(walk(root * 2, left, mid, qleft, qright, val),
walk(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
void dynamic()
{
for (int i = 1; i <= n; i ++)
{
ll free_time = s[i] - pref[0][i];
int lf = 0, rf = m;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (pref[1][mf] <= free_time)
lf = mf + 1;
else
rf = mf - 1;
}
X[i] = rf;
/**while(X[i] <= m && pref[1][X[i]] <= free_time)
X[i] ++;
X[i] --;*/
upd[i - 1].push_back({X[i] + 1, - p[i]});
///cout << "point " << i - 1 << " " << X[i] + 1 << " " << -p[i] << endl;
}
for (int i = 1; i <= m; i ++)
{
ll free_time = t[i] - pref[1][i];
int lf = 0, rf = n;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (pref[0][mf] <= free_time)
lf = mf + 1;
else
rf = mf - 1;
}
Y[i] = rf;
/**while(Y[i] <= n && pref[0][Y[i]] <= free_time)
Y[i] ++;
Y[i] --;*/
if (Y[i] >= 0)
{
upd[Y[i]].push_back({i, q[i]});
//cout << "point " << Y[i] << " " << i << " " << q[i] << endl;
}
}
for (int j = 0; j <= m; j ++)
dp[j] = 0;
for (pair < int, ll > cur : upd[0])
for (int d = cur.first; d <= m; d ++)
dp[d] += cur.second;
for (int i = 1; i <= m; i ++)
dp[i] = max(dp[i], dp[i - 1]);
build(1, 0, m);
for (int i = 1; i <= n; i ++)
{
sort(upd[i].begin(), upd[i].end());
/**cout << "--------------" << endl;
for (int j = 0; j <= m; j ++)
{
cout << dp[j] << " " << query(1, 0, m, j) << endl;
}*/
ll sum = 0;
for (int j = 0; j < upd[i].size(); j ++)
{
int cur = upd[i][j].first;
int nxt = m + 1;
if (j + 1 < upd[i].size())
nxt = upd[i][j + 1].first;
sum += upd[i][j].second;
if (upd[i][j].first == 0 || i == n)
{
range_add(1, 0, m, cur, nxt - 1, sum);
//for (int d = cur; d < nxt; d ++)
// dp[d] += sum;
}
else
{
ll bef = query(1, 0, m, upd[i][j].first - 1);
int last = max(nxt - 1, walk(1, 0, m, cur, nxt - 1, bef - sum));
/**int lf = cur, rf = nxt - 1;
while(lf <= rf)
{
int mf= (lf + rf) / 2;
if (query(1, 0, m, mf) + sum < bef)
lf = mf + 1;
else
rf = mf - 1;
}
last = lf - 1;*/
/**for (int d = cur; d < nxt; d ++)
{
if (query(1, 0, m, d) + sum < bef)
last = d;
}*/
set_range(1, 0, m, cur, last, bef);
range_add(1, 0, m, last + 1, nxt - 1, sum);
/**for (int d = cur; d <= last; d ++)
dp[d] = bef;
for (int d = last + 1; d < nxt; d ++)
dp[d] += sum;*/
}
}
/*for (pair < int, ll > cur : upd[i])
{
sum += cur.second;
ll var = dp[cur.first] + sum;
//cout << "update point " << cur.first << " " << cur.second << endl;
for (int d = cur.first; d <= m; d ++)
{
temp[d] += cur.second;
}
}
for (int j = 0; j <= m; j ++)
{
///best = max(best, dp[j]);
dp[j] += temp[j];
}
if (i != n)
{
for (int j = 1; j <= m; j ++)
dp[j] = max(dp[j - 1], dp[j]);
}*/
/**cout << "state " << i << endl;
for (int j = 0; j <= m; j ++)
cout << dp[j] << " ";
cout << endl;*/
}
ll res = 0;
for (int i = 1; i <= n; i ++)
res += p[i];
res = res + query(1, 0, m, m);
cout << res << endl;
/**for (int i = 0; i <= n; i ++)
{
for (int j = 0; j <= m; j ++)
{
if (i > 0)
{
dp[i][j] = max(dp[i][j], dp[i - 1][j] + (pref[0][i] + pref[1][j] <= s[i]));
}
if (j > 0)
{
dp[i][j] = max(dp[i][j], dp[i][j - 1] + (pref[0][i] + pref[1][j] <= t[j]));
}
///cout << "state " << i << " " << j << " " << dp[i][j] << endl;
}
}
cout << dp[n][m] << endl;*/
}
void solve()
{
input();
prefix_sums();
dynamic();
}
int main()
{
speed();
solve();
return 0;
}
/**
9 12
414814218 278771326 1
142790158 568604393 1
155567225 14012701 1
627555390 1224920860 1
677068511 5243031298 1
580933994 8598159379 1
819258172 1432469030 1
340548310 999347990 1
432162069 4373255579 1
99824657 11080715 1
756309567 9502204999 1
929699364 2343419815 1
376204577 6097684636 1
399553538 2306014840 1
824786328 4994974413 1
536419761 3247725215 1
953903194 10674273733 1
787043482 3936134684 1
105275489 567691865 1
861537554 117255456 1
434345770 2420939138 1
*/
Compilation message
dishes.cpp: In function 'int walk(int, int, int, int, int, ll)':
dishes.cpp:160:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
160 | if (left == right)
| ^~
dishes.cpp:163:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
163 | int mid = (left + right) / 2;
| ^~~
dishes.cpp: In function 'void dynamic()':
dishes.cpp:251:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
251 | for (int j = 0; j < upd[i].size(); j ++)
| ~~^~~~~~~~~~~~~~~
dishes.cpp:255:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | if (j + 1 < upd[i].size())
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
459 ms |
93768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
49728 KB |
Output is correct |
| 2 |
Correct |
11 ms |
49620 KB |
Output is correct |
| 3 |
Correct |
8 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
11 ms |
49500 KB |
Output is correct |
| 6 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
49500 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
49728 KB |
Output is correct |
| 2 |
Correct |
11 ms |
49620 KB |
Output is correct |
| 3 |
Correct |
8 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
11 ms |
49500 KB |
Output is correct |
| 6 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
49500 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
49728 KB |
Output is correct |
| 2 |
Correct |
11 ms |
49620 KB |
Output is correct |
| 3 |
Correct |
8 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
11 ms |
49500 KB |
Output is correct |
| 6 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
49500 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
49728 KB |
Output is correct |
| 2 |
Correct |
11 ms |
49620 KB |
Output is correct |
| 3 |
Correct |
8 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
11 ms |
49500 KB |
Output is correct |
| 6 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
49500 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
49728 KB |
Output is correct |
| 2 |
Correct |
11 ms |
49620 KB |
Output is correct |
| 3 |
Correct |
8 ms |
49884 KB |
Output is correct |
| 4 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
11 ms |
49500 KB |
Output is correct |
| 6 |
Correct |
9 ms |
49500 KB |
Output is correct |
| 7 |
Incorrect |
9 ms |
49500 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
459 ms |
93768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
459 ms |
93768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
