#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e18;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],seg[2200000],lazy[2200000],c[1100000],d[1100000],cost[1100000],add_cost[1100000],dp[1100000];
ll sum1[1100000],range[1100000],sum2[1100000];
vector<ll> del_list[1100000];
set<pair<ll,ll>> chain;
pair<ll,ll> p,q;
pair<ll,ll> find_chain(ll x)
{
pair<ll,ll> p=*(--chain.lower_bound(make_pair(x,inf)));
return p;
}
void propagate(ll x,ll y,ll z)
{
if(z<1048576)
{
lazy[z*2]+=lazy[z];
lazy[z*2+1]+=lazy[z];
}
seg[z]+=lazy[z];
lazy[z]=0;
}
void f(ll x,ll y,ll z,ll w)
{
propagate(x,y,z);
if(y<l||x>r)
return;
if(l<=x&&y<=r)
{
lazy[z]+=w;
propagate(x,y,z);
return;
}
f(x,(x+y)/2,z*2,w);
f((x+y)/2+1,y,z*2+1,w);
seg[z]=max(seg[z*2],seg[z*2+1]);
}
ll g(ll x,ll y,ll z)
{
propagate(x,y,z);
if(y<l||x>r)
{
return -inf;
}
if(l<=x&&y<=r)
{
return seg[z];
}
return max(g(x,(x+y)/2,z*2),g((x+y)/2+1,y,z*2+1));
}
void add(ll x,ll y,ll z)
{
l=x+1;
r=y+1;
f(1,1048576,1,z);
}
ll get_val(ll x)
{
l=x+1;
r=x+1;
return g(1,1048576,1);
}
void reconstruct_chain(ll x)
{
pair<ll,ll> p=find_chain(x);
while(chain.upper_bound(p)!=chain.end())
{
pair<ll,ll> q=(*chain.upper_bound(p));
y=get_val(p.second);
z=get_val(q.first);
//printf("(%lld,%lld,%lld,%lld)\n",p.first,p.second,q.first,q.second);
if(z<=y+cost[p.second])
{
add(q.first,q.second,y+cost[p.second]-z);
chain.erase(p);
chain.erase(q);
chain.insert({p.first,q.second});
p.second=q.second;
}
else
return;
}
}
void show()
{
return;
ll i;
for(i=0;i<=m;i++)
printf("%lld ",get_val(i));
printf("\n");
}
int main()
{
scanf("%lld %lld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
sum1[i]=sum1[i-1]+a[i];
}
for(i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
sum2[i]=sum2[i-1]+b[i];
}
for(i=1;i<=n;i++)
{
range[i]=upper_bound(sum2,sum2+m+1,c[i]-sum1[i])-sum2-1;
//printf("(%lld) ",range[i]);
}
//printf("\n");
for(i=1;i<=m;i++)
{
x=upper_bound(sum1,sum1+n+1,d[i]-sum2[i])-sum1;
del_list[x].push_back(i-1);
//printf("(%lld)",x);
}
//printf("\n");
for(auto xx:del_list[0])
{
cost[xx]=0;
}
for(i=1;i<=m;i++)
{
dp[i]=dp[i-1]+cost[i-1];
}
for(i=0;i<=m;i++)
{
add(i,i,dp[i]);
}
/*for(i=0;i<=m;i++)
{
printf("(%lld)",cost[i]);
}
printf("\n");
*/chain.insert({0,m});
for(i=1;i<=n;i++)
{show();
for(auto xx:del_list[i])
{
//printf("{%lld}\n",xx);
if(cost[xx]>0)
{
continue;
p=find_chain(xx);
chain.erase(p);
chain.insert({p.first,xx});
if(xx+1<=p.second)
chain.insert({xx+1,p.second});
cost[xx]=0;
}
else
{
continue;
p=find_chain(xx);
add(xx+1,p.second,-cost[xx]);
cost[xx]=0;
reconstruct_chain(xx);
}
}
x=range[i];
p=find_chain(x);
if(x==-1)
continue;
if(add_cost[i]>0)
{
add(0,p.second,add_cost[i]);
//printf("[%lld,%lld]\n",x,cost[x]);
reconstruct_chain(x);
}
else
{
chain.erase(p);
chain.insert({p.first,x});
if(x+1<=p.second)
chain.insert({x+1,p.second});
add(0,x,add_cost[i]);
reconstruct_chain(x);
}
for(auto xx:del_list[i])
{
//printf("{%lld}\n",xx);
if(cost[xx]>0)
{
p=find_chain(xx);
chain.erase(p);
chain.insert({p.first,xx});
if(xx+1<=p.second)
chain.insert({xx+1,p.second});
cost[xx]=0;
}
else
{
p=find_chain(xx);
add(xx+1,p.second,-cost[xx]);
cost[xx]=0;
reconstruct_chain(xx);
}
}
}
s=-inf;
show();
for(i=m;i<=m;i++)
{
s=max(s,get_val(i));
}
printf("%lld",s);
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%lld %lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
dishes.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%lld %lld %lld",&a[i],&c[i],&add_cost[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%lld %lld %lld",&b[i],&d[i],&cost[i-1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
341 ms |
73940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
26460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
26460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
26460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
26460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
26460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
341 ms |
73940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
341 ms |
73940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
