Submission #1038695

#TimeUsernameProblemLanguageResultExecution timeMemory
1038695ibm2006Two Dishes (JOI19_dishes)C++17
0 / 100
341 ms73940 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...