#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()
{
ios::sync_with_stdio(false);
cin.tie(0);
//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-1)});
}
}
//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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
675 ms |
62356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
23800 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
675 ms |
62356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
675 ms |
62356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
