Submission #120197

#TimeUsernameProblemLanguageResultExecution timeMemory
120197KLPPTwo Dishes (JOI19_dishes)C++14
10 / 100
10086 ms176356 KiB
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 10000000000000000
lld n,m;
lld a[1000000];
lld b[1000000];
lld sa[1000000];
lld sb[1000000];
lld s[1000000];
lld t[1000000];
lld p[1000000];
lld q[1000000];

/*class ST{
  lld arr[4000000];
  lld lazy[4000000];
public:
  void build(int a, int b, int node){
    arr[node]=0;
    lazy[node]=0;
    if(a==b)return;
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
  }
  void propagate(int a, int b, int node){
    arr[node]+=(b-a+1)*lazy[node];
    if(a!=b){
      lazy[2*node]+=lazy[node];
      lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
  }
  void update(int a, int b, int node, int x,int y, lld val){
    propagate(a,b,node);
    if(y<a || b<x)return;
    if(x<=a && b<=y){
      lazy[node]+=val;
      propagate(a,b,node);
      return;
    }
    int mid=(a+b)/2;
    update(a,mid,2*node,x,y,val);
    update(mid+1,b,2*node+1,x,y,val);
    arr[node]=arr[2*node]+arr[2*node+1];
  }
  lld query(int a, int b, int node, int x, int y){
    propagate(a,b,node);
    if(b<x || y<a)return 0;
    if(x<=a && b<=y)return arr[node];
    int mid=(a+b)/2;
    return query(a,mid,2*node,x,y)+query(mid+1,b,2*node+1,x,y);
  }
};*/
struct node{
  lld val;
  node *l,*r;
};
void extend(node *n){
  if(!n->l){
    n->l=new node();
    n->r=new node();
    n->l->val=0;
    n->r->val=0;
  }
}
void update(node *n, int a, int b, int pos, lld val, node *m){
  if(pos<a || b<pos)return;
  if(a==b){
    m->val=val;
    return;
  }
  extend(m);
  int mid=(a+b)/2;
  if(pos<=mid){
    //if(!n->r)cout<<"ERR"<<endl;
    m->r=n->r;
    update(n->l,a,mid,pos,val,m->l);
  }else{
    m->l=n->l;
    update(n->r,mid+1,b,pos,val,m->r);
  }
  m->val=m->l->val+m->r->val;
}
lld query(node *n, int a, int b, int x, int y){
  if(b<x || y<a)return 0;
  if(x<=a && b<=y)return n->val;
  int mid=(a+b)/2;
  return query(n->l,a,mid,x,y)+query(n->r,mid+1,b,x,y);
}
void init(node *n, int x, int y){
  if(x==y){
    n->val=q[x];
    return;
  }
  extend(n);
  int mid=(x+y)/2;
  init(n->l,x,mid);
  init(n->r,mid+1,y);
  n->val=n->l->val+n->r->val;
}
void print(node *n, int x, int y){
  if(!n)return;
  cout<<n->val<<" "<<x<<" "<<y<<endl;
  if(x==y)return;
  int mid=(x+y)/2;
  print(n->l,x,mid);
  print(n->r,mid+1,y);
}
class DS{
  node *ST[1000000];
  pii troc[1000000];
  int step;
  int ptr;
  lld arr[1000000];
public:
  void Init(){
    step=0;
    ptr=0;
    rep(i,0,m+1){
      ST[i]=new node();
    }
    init(ST[0],0,(int)m-1);
    rep(i,0,m){
      int lo,hi;
      lo=-1;
      hi=n+1;
      while(hi-lo>1){
	int mid=(hi+lo)/2;
	if(sa[mid]+sb[i+1]<=t[i]){
	  lo=mid;
	}else hi=mid;
      }
      troc[i]=pii(lo,i);
      //cout<<lo<<" "<<hi<<endl;
    }
    sort(troc,troc+m);
    arr[0]=0;
    rep(i,1,m+1){
      if(sb[i]<=t[i-1])arr[i]=arr[i-1]+q[i-1];
      else arr[i]=arr[i-1];
      //cout<<arr[i]<<" "<<arr[i-1]<<" "<<sb[i]<<" "<<t[i-1]<<endl;
    }
    //print(ST[0],0,m-1);
    /*rep(i,0,m+1)cout<<arr[i]<<" ";
      cout<<endl;*/
  }
  void Step(){
    while(ptr<m && troc[ptr].first<=step){
      update(ST[ptr],0,m-1,troc[ptr].second,0,ST[ptr+1]);
      //print(ST[ptr+1],0,m-1);
      ptr++;
    }
    int lo,hi;
    lo=-1;
    hi=m+1;
    while(hi-lo>1){
      int mid=(lo+hi)/2;
      if(sa[step+1]+sb[mid]<=s[step]){
	lo=mid;
      }else hi=mid;
    }
    //cout<<lo<<" "<<hi<<" "<<sa[step+1]+sb[hi]<<" "<<s[step]<<" "<<step<<endl;
    if(lo==-1){
      /*rep(i,0,m+1)cout<<arr[i]<<" ";
      cout<<endl;*/
      step++;
      return;

    }
    //cout<<lo<<endl;
    lld V=arr[lo];
    //cout<<V<<endl;
    rep(i,0,hi){
      arr[i]+=p[step];
    }
    rep(i,hi,m+1){
      arr[i]=max(arr[i],arr[lo]+query(ST[ptr],0,m-1,lo,i-1));
    }
    /*rep(i,0,m+1)cout<<arr[i]<<" ";
      cout<<endl;*/
    step++;
  }
  lld val(int pos){
    return arr[pos];
  }
};
int main(){
  scanf("%lld %lld",&n,&m);
  rep(i,0,n)scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
  rep(i,0,m)scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
  sa[0]=0;
  sb[0]=0;
  rep(i,1,n+1){
    sa[i]=sa[i-1]+a[i-1];
  }
  rep(i,1,m+1){
    sb[i]=sb[i-1]+b[i-1];
  }
  DS *D=new DS();
  D->Init();
  
  rep(i,0,n){
    D->Step();
  }
  cout<<D->val(m)<<endl;
  //cout<<query(ST,0,n-1,0,2)<<endl;
  return 0;
}

Compilation message (stderr)

dishes.cpp: In member function 'void DS::Step()':
dishes.cpp:177:9: warning: unused variable 'V' [-Wunused-variable]
     lld V=arr[lo];
         ^
dishes.cpp: In function 'int main()':
dishes.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&n,&m);
   ~~~~~^~~~~~~~~~~~~~~~~~~
dishes.cpp:195:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   rep(i,0,n)scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:196:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   rep(i,0,m)scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...