#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=100000000000000000;
int it[4100000];
pair<int, int> lazy[4100000];
pair<int, int> merge(pair<int, int> u, pair<int, int> v)
{
return {u.first+v.first, max(u.second, v.second+u.first)};
}
void down(int id, int l, int r)
{
it[id]=max(it[id]+lazy[id].first, lazy[id].second);
if(true)
{
lazy[id*2]=merge(lazy[id], lazy[id*2]);
lazy[id*2+1]=merge(lazy[id], lazy[id*2+1]);
}
lazy[id]={0, -inf};
}
void update(int id, int l, int r, int u, int v, pair<int, int> val)
{
down(id, l, r);
if(l>v||r<u)
{
return;
}
if(l>=u&&r<=v)
{
lazy[id]=val;
down(id, l, r);
return;
}
int mid=(l+r)/2;
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
it[id]=max(it[id*2], it[id*2+1]);
}
int get(int id, int l, int r, int pos)
{
down(id, l, r);
if(l==r) return it[id];
int mid=(l+r)/2;
if(pos<=mid) return get(id*2, l, mid, pos);
else return get(id*2+1, mid+1, r, pos);
}
int a[1000005], s[1000005], p[1000005];
int b[1000005], t[1000005], q[1000005];
int n, m;
vector<pair<int, int> > events[1000005];
signed main()
{
//update(1,0,5,1,5,{1,0});
//update(1,0,5,1,5,{1,0});
//cout<<get(1,0,5,4);
//return 0;
//freopen("dishes.inp", "r", stdin);
//freopen("dishes.out", "w", stdout);
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>a[i]>>s[i]>>p[i];
a[i]+=a[i-1];
}
for(int i=1; i<=m; i++)
{
cin>>b[i]>>t[i]>>q[i];
b[i]+=b[i-1];
}
int dora=0;
for(int i=1; i<=n; i++)
{
int ok=upper_bound(b, b+m+1, s[i]-a[i])-b;
if(ok>=1)
{
events[ok-1].push_back({i, p[i]});
}
}
for(int i=1; i<=m; i++)
{
dora+=q[i]; q[i]=-q[i];
int ok=upper_bound(a, a+n+1, t[i]-b[i])-a;
if(ok<=n)
{
events[i-1].push_back({ok, q[i]});
}
}
fill(lazy, lazy+n*4+5, (pair<int, int>){0, -inf});
for(int p=0; p<m; p++)
{
for(auto i:events[p])
{
//cout<<i.first<<" "<<i.second<<endl;
update(1, 0, n, i.first, n, {i.second, -inf});
}
for(auto i:events[p])
{
if(i.first)
{
//cout<<get(1, 0, n, i.first)<<endl;
update(1, 0, n, i.first, n, {0, get(1, 0, n, i.first)});
}
}
for(int i=0; i<=n; i++)
{
//cout<<get(1, 0, n, i)<<" ";
}
//cout<<endl;
}
for(auto i:events[m])
{
update(1, 0, n, i.first, n, {i.second, -inf});
}
cout<<dora-get(1, 0, n, n);
}
Compilation message
dishes.cpp:99:2: error: stray '\302' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:3: error: stray '\240' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:5: error: stray '\302' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:6: error: stray '\240' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:8: error: stray '\302' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:9: error: stray '\240' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:11: error: stray '\302' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:12: error: stray '\240' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:14: error: stray '\302' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:15: error: stray '\240' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:17: error: stray '\302' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:99:18: error: stray '\240' in program
//cout<<i.first<<" "<<i.second<<endl;
^
dishes.cpp:106:2: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:3: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:5: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:6: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:8: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:9: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:11: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:12: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:14: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:15: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:17: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:18: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:20: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:21: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:23: error: stray '\302' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:106:24: error: stray '\240' in program
//cout<<get(1, 0, n, i.first)<<endl;
^
dishes.cpp:112:2: error: stray '\302' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:3: error: stray '\240' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:5: error: stray '\302' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:6: error: stray '\240' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:8: error: stray '\302' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:9: error: stray '\240' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:11: error: stray '\302' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:12: error: stray '\240' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:14: error: stray '\302' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:112:15: error: stray '\240' in program
//cout<<get(1, 0, n, i)<<" ";
^
dishes.cpp:114:2: error: stray '\302' in program
//cout<<endl;
^
dishes.cpp:114:3: error: stray '\240' in program
//cout<<endl;
^
dishes.cpp:114:5: error: stray '\302' in program
//cout<<endl;
^
dishes.cpp:114:6: error: stray '\240' in program
//cout<<endl;
^
dishes.cpp:114:8: error: stray '\302' in program
//cout<<endl;
^
dishes.cpp:114:9: error: stray '\240' in program
//cout<<endl;
^
