#include <bits/stdc++.h>
using namespace std;
const int SZ = 1e6 + 5;
const long long INF = 1e18;
int n, m;
long long Arb[4000015], Lazy_scad[4000015], Lazy_max[4000015];
long long a[SZ], b[SZ], s[SZ], s1[SZ], s2[SZ], t[SZ], q[SZ], p[SZ];
void propag_scad(int nod){
if(Lazy_scad[nod] != 0){
Arb[nod * 2] += Lazy_scad[nod];
Arb[nod * 2 + 1] += Lazy_scad[nod];
Lazy_scad[nod * 2] += Lazy_scad[nod];
Lazy_scad[nod * 2 + 1] += Lazy_scad[nod];
Lazy_scad[nod] = 0;
}
}
void propag_max(int nod){
if(Lazy_max[nod] != -INF){
Arb[nod * 2] = max(Arb[nod * 2], Lazy_max[nod]);
Arb[nod * 2 + 1] = max(Arb[nod * 2 + 1], Lazy_max[nod]);
Lazy_max[nod * 2] = max(Lazy_max[nod * 2], Lazy_max[nod]);
Lazy_max[nod * 2 + 1] = max(Lazy_max[nod * 2 + 1], Lazy_max[nod]);
Lazy_max[nod] = -INF;
}
}
void update_scad(int x, int y, long long v, int st = 0, int dr = m, int nod = 1){
if(st != dr) propag_scad(nod), propag_max(nod);
if(x <= st && dr <= y){
Lazy_scad[nod] += v;
Arb[nod] += v;
return ;
}
int mij = (st + dr) / 2;
if(x <= mij) update_scad(x, y, v, st, mij, nod * 2);
if(mij + 1 <= y) update_scad(x, y, v, mij + 1, dr, nod * 2 + 1);
Arb[nod] = max(Arb[nod * 2], Arb[nod * 2 + 1]);
}
void update_max(int x, int y, long long v, int st = 0, int dr = m, int nod = 1){
if(st != dr) propag_scad(nod), propag_max(nod);
if(x <= st && dr <= y){
Lazy_max[nod] = max(v, Lazy_max[nod]);
Arb[nod] = max(v, Arb[nod]);
return ;
}
int mij = (st + dr) / 2;
if(x <= mij) update_max(x, y, v, st, mij, nod * 2);
if(mij + 1 <= y) update_max(x, y, v, mij + 1, dr, nod * 2 + 1);
Arb[nod] = max(Arb[nod * 2], Arb[nod * 2 + 1]);
}
long long query(int x, int y, int st = 0, int dr = m, int nod = 1){
if(x <= st && dr <= y) return Arb[nod];
if(st != dr) propag_scad(nod), propag_max(nod);
int mij = (st + dr) / 2;
long long a1 = -INF, a2 = -INF;
if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);
return max(a1, a2);
}
vector <pair <int, long long> > v[SZ];
void add_point(int x, int y, long long val){
v[x].push_back({y, val});
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= 4 * m + 4 ; ++i) Lazy_max[i] = -INF;
for(int i = 1; i <= n ; ++i){
scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
s1[i] = s1[i - 1] + a[i];
}
for(int i = 1; i <= m ; ++i){
scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
s2[i] = s2[i - 1] + b[i];
}
long long Sum = 0;
for(int i = 1; i <= n ; ++i){
long long v = s[i] - s1[i];
if(v < 0) continue ;
int st = 1, dr = m;
while(st <= dr){
int mij = (st + dr) / 2;
if(s2[mij] <= v) st = mij + 1;
else dr = mij - 1;
}
if(dr < m) add_point(i - 1, dr + 1, -p[i]);
Sum += p[i];
}
for(int i = 1; i <= m ; ++i){
long long v = t[i] - s2[i];
if(v < 0) continue ;
int st = 1, dr = n;
while(st <= dr){
int mij = (st + dr) / 2;
if(s1[mij] <= v) st = mij + 1;
else dr = mij - 1;
}
add_point(dr, i, q[i]);
}
for(int i = 0; i <= n ; ++i){
if(i > 0){
for(auto it : v[i - 1]){
val = query(0, it.first);
update_max(it.first, m, val);
}
}
for(auto it : v[i]) update_scad(it.first, m, it.second);
}
printf("%lld", Sum + Arb[1]);
return 0;
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:136:17: error: 'val' was not declared in this scope
val = query(0, it.first);
^~~
dishes.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
