#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=1e18;
ll a[N],s[N],p[N],b[N],t[N],q[N];
vector<pair<int,ll>> Qs[N];
//Segment Tree Beats
/*int ls[M],rs[M],tsz,root;
ll mx[M],lzy_add[M],lzy[M],fir[M],sec[M];
void Build(int &c, int ss, int se)
{
c=++tsz;mx[c]=0;lzy_add[c]=0;lzy[c]=-inf;fir[c]=0;sec[c]=inf;
if(ss==se) return;
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
}
void upd(int c, ll add, ll x)
{
fir[c]+=add;sec[c]+=add;
fir[c]=max(fir[c],x);
sec[c]=max(sec[c],x);
lzy_add[c]+=add;
lzy[c]+=add;
lzy[c]=max(lzy[c],x);
}
void push(int c)
{
upd(ls[c],lzy_add[c],lzy[c]);
upd(rs[c],lzy_add[c],lzy[c]);
lzy_add[c]=0;
lzy[c]=-inf;
}
void pull(int c)
{
if(fir[ls[c]]>fir[rs[c]])
{
fir[c]=fir[rs[c]];
sec[c]=min(fir[ls[c]],sec[rs[c]]);
}
else if(fir[ls[c]]<fir[rs[c]])
{
fir[c]=fir[ls[c]];
sec[c]=min(sec[ls[c]],fir[rs[c]]);
}
else
{
fir[c]=fir[ls[c]];
sec[c]=min(sec[ls[c]],sec[rs[c]]);
}
}
void Add(int c, int ss, int se, int qs, int qe, ll add)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se){ upd(c,add,-inf);return;}
push(c);
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,add);
Add(rs[c],mid+1,se,qs,qe,add);
pull(c);
}
void Set(int c, int ss, int se, int qs, int qe, ll x)
{
if(qs>qe || qs>se || ss>qe || fir[c]>=x) return;
if(qs<=ss && qe>=se && sec[c]>x){ upd(c,0,x);return;}
push(c);
int mid=ss+se>>1;
Set(ls[c],ss,mid,qs,qe,x);
Set(rs[c],mid+1,se,qs,qe,x);
pull(c);
}
ll Get(int c, int ss, int se, int qi)
{
if(ss==se) return fir[c];
push(c);
int mid=ss+se>>1;
if(qi<=mid) return Get(ls[c],ss,mid,qi);
else return Get(rs[c],mid+1,se,qi);
}
void Print(int c, int ss, int se)
{
printf("(%i %i) %lld %lld lzy:%lld add:%lld\n",ss,se,fir[c],sec[c],lzy[c],lzy_add[c]);
if(ss==se) return;
int mid=ss+se>>1;
Print(ls[c],ss,mid);
Print(rs[c],mid+1,se);
}*/
struct SegmentTreeBeats
{
int root,tsz,ls[M],rs[M],n;
ll fir[M],sec[M],lzy[M],lzy_add[M];
SegmentTreeBeats(){}
void upd(int c, ll add, ll x)
{
fir[c]+=add;
sec[c]+=add;
fir[c]=max(fir[c],x);
lzy_add[c]+=add;
if(lzy[c]!=-inf) lzy[c]+=add;
lzy[c]=max(lzy[c],x);
}
void push(int c)
{
if(lzy_add[c]!=0 || lzy[c]!=-inf)
{
upd(ls[c],lzy_add[c],lzy[c]);
upd(rs[c],lzy_add[c],lzy[c]);
lzy_add[c]=0;
lzy[c]=-inf;
}
}
void pull(int c)
{
set<ll> st;
st.insert(fir[ls[c]]);
st.insert(sec[ls[c]]);
st.insert(fir[rs[c]]);
st.insert(sec[rs[c]]);
auto it=st.begin();
fir[c]=*it;
it++;
sec[c]=*it;
}
void Build(int &c, int ss, int se)
{
c=++tsz;fir[c]=0;sec[c]=inf;lzy_add[c]=0;lzy[c]=-inf;
if(ss==se) return;
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
}
void Add(int c, int ss, int se, int qs, int qe, ll f)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se){ upd(c,f,-inf);return;}
push(c);
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,f);
Add(rs[c],mid+1,se,qs,qe,f);
pull(c);
}
void Set(int c, int ss, int se, int qs, int qe, ll x)
{
if(qs>qe || qs>se || ss>qe || fir[c]>=x) return;
if(qs<=ss && qe>=se && sec[c]>x){ upd(c,0,x);return;}
push(c);
int mid=ss+se>>1;
Set(ls[c],ss,mid,qs,qe,x);
Set(rs[c],mid+1,se,qs,qe,x);
pull(c);
}
ll Get(int c, int ss, int se, int qi)
{
if(ss==se) return fir[c];
push(c);
int mid=ss+se>>1;
if(qi<=mid) return Get(ls[c],ss,mid,qi);
else return Get(rs[c],mid+1,se,qi);
}
void init(int _n){ n=_n;Build(root,0,n);}
void Add(int qs, int qe, ll f){ Add(root,0,n,qs,qe,f);}
void Set(int qs, int qe, ll x){ Set(root,0,n,qs,qe,x);}
ll Get(int qi){ return Get(root,0,n,qi);}
} STB;
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];
ll sum=0;
STB.init(m);
//Build(root,0,m);
for(int i=1;i<=m;i++)
{
int j=upper_bound(a,a+1+n,t[i]-b[i])-a;
if(j)
{
sum+=q[i];
Qs[j].pb({i-1,-q[i]});
}
}
for(int i=1;i<=n;i++)
{
int j=upper_bound(b,b+1+m,s[i]-a[i])-b;
if(j) Qs[i].pb({j-1,p[i]});
sort(Qs[i].rbegin(),Qs[i].rend());
for(auto qu:Qs[i])
{
int p=qu.first;
ll f=qu.second;
//Add(root,0,m,0,p,f);
STB.Add(0,p,f);
//printf("Add:%i %i %lld\n",0,p,f);
//Print(root,0,m);
//ll g=Get(root,0,m,p);
ll g=STB.Get(p);
//Set(root,0,m,p+1,m,g);
STB.Set(p,m,g);
//printf("Set:%i %i %lld\n",p+1,m,g);
//Print(root,0,m);
}
}
//printf("%lld\n",Get(root,0,m,m)+sum);
printf("%lld\n",STB.Get(m)+sum);
return 0;
}
Compilation message
dishes.cpp: In member function 'void SegmentTreeBeats::Build(int&, int, int)':
dishes.cpp:131:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In member function 'void SegmentTreeBeats::Add(int, int, int, int, int, long long int)':
dishes.cpp:140:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In member function 'void SegmentTreeBeats::Set(int, int, int, int, int, long long int)':
dishes.cpp:150:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In member function 'long long int SegmentTreeBeats::Get(int, int, int, int)':
dishes.cpp:159:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:171: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:172: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:173: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 |
Correct |
1871 ms |
58536 KB |
Output is correct |
| 2 |
Incorrect |
1933 ms |
59464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1871 ms |
58536 KB |
Output is correct |
| 2 |
Incorrect |
1933 ms |
59464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1871 ms |
58536 KB |
Output is correct |
| 2 |
Incorrect |
1933 ms |
59464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
