#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1000050;
const int M=2*N;
const ll inf=9e18;
int ls[M],rs[M],tsz,root;
ll lzy[M][2],mx[M];
void Upd(int c, ll x, int t){ t==0?mx[c]+=x,lzy[c][0]+=x,lzy[c][1]+=x:mx[c]=max(mx[c],x),lzy[c][1]=max(lzy[c][1],x);}
void Push(int c){ Upd(ls[c],lzy[c][0],0);Upd(ls[c],lzy[c][1],1);Upd(rs[c],lzy[c][0],0);Upd(rs[c],lzy[c][1],1);lzy[c][0]=0;lzy[c][1]=-inf;}
void Set(int c, int ss, int se, int qs, int qe, ll x, int t)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se) return Upd(c,x,t);
int mid=ss+se>>1;
Push(c);
Set(ls[c],ss,mid,qs,qe,x,t);
Set(rs[c],mid+1,se,qs,qe,x,t);
mx[c]=max(mx[ls[c]],mx[rs[c]]);
}
ll Get(int c, int ss, int se, int qs, int qe)
{
if(qs>qe || qs>se || ss>qe || !c) return -inf;
if(qs<=ss && qe>=se) return mx[c];
int mid=ss+se>>1;
Push(c);
return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
void Build(int &c, int ss, int se)
{
c=++tsz;lzy[c][1]=-inf;
if(ss==se) return;
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
}
ll a[N],s[N],p[N],b[N],t[N],q[N];
vector<pair<int,int>> Us[N];
int main()
{
int n,m;
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
for(int i=1;i<=n;i++)
{
int j=upper_bound(b,b+m+1,s[i]-a[i])-b-1;
if(j>=0) Us[j].pb({i,p[i]});
}
ll sum=0;
for(int i=1;i<=m;i++)
{
sum+=q[i];
int j=upper_bound(a,a+n+1,t[i]-b[i])-a;
if(j<=n) Us[i-1].pb({j,-q[i]});
}
Build(root,0,n);
for(int i=0;i<=m;i++)
{
for(auto u:Us[i]) Set(root,0,n,u.first,n,u.second,0);
for(auto u:Us[i]) Set(root,0,n,u.first,n,Get(root,0,n,0,u.first-1),1);
}
printf("%lld\n",sum+Get(root,0,n,0,n));
return 0;
}
Compilation message
dishes.cpp: In function 'void Set(int, int, int, int, int, long long int, int)':
dishes.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In function 'long long int Get(int, int, int, int, int)':
dishes.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In function 'void Build(int&, int, int)':
dishes.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
dishes.cpp:44:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
dishes.cpp:45:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
711 ms |
66296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23880 KB |
Output is correct |
4 |
Correct |
33 ms |
23900 KB |
Output is correct |
5 |
Correct |
24 ms |
23900 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23880 KB |
Output is correct |
4 |
Correct |
33 ms |
23900 KB |
Output is correct |
5 |
Correct |
24 ms |
23900 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23880 KB |
Output is correct |
4 |
Correct |
33 ms |
23900 KB |
Output is correct |
5 |
Correct |
24 ms |
23900 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23880 KB |
Output is correct |
4 |
Correct |
33 ms |
23900 KB |
Output is correct |
5 |
Correct |
24 ms |
23900 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23928 KB |
Output is correct |
2 |
Correct |
24 ms |
23800 KB |
Output is correct |
3 |
Correct |
24 ms |
23880 KB |
Output is correct |
4 |
Correct |
33 ms |
23900 KB |
Output is correct |
5 |
Correct |
24 ms |
23900 KB |
Output is correct |
6 |
Correct |
24 ms |
23800 KB |
Output is correct |
7 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
711 ms |
66296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
711 ms |
66296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |