Submission #120198

#	Time	Username	Problem	Language	Result	Execution time	Memory
120198		KLPP	Two Dishes (JOI19_dishes)	C++14	10 / 100	10107 ms	299216 KiB

dishes

#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];
  lld Lazy[4000000];
  lld Lazy2[4000000][3];
public:
  void Build(int a, int b, int node){
    Lazy[node]=0;
    Lazy2[node][0]=-1;//Valor
    Lazy2[node][1]=-1;//Indice
    Lazy2[node][2]=-1;//Versao
    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){
    if(a==b){
      if(Lazy2[node][0]!=-1)arr[a]=Lazy2[node][0]+query(ST[Lazy2[node][2]],0,m-1,Lazy2[node][1],a-1);
      rep(j,0,3)Lazy2[node][j]=-1;
      arr[a]+=Lazy[node];
      Lazy[node]=0;
      return;
    }
    if(Lazy2[node][0]!=-1){
      rep(i,0,3){
	rep(j,0,2)Lazy2[2*node+j][i]=Lazy2[node][i];
	Lazy2[node][i]=-1;
      }
      Lazy[2*node]=0;
      Lazy[2*node+1]=0;
    }
    Lazy[2*node]+=Lazy[node];
    Lazy[2*node+1]+=Lazy[node];
    Lazy[node]=0;
    
  }
  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;
    }
    Build(0,m,1);
    //print(ST[0],0,m-1);
    /*rep(i,0,m+1)cout<<arr[i]<<" ";
      cout<<endl;*/
  }
  void Update1(int a, int b, int node, int x, int y,lld val){
    propagate(a,b,node);
    if(b<x || y<a)return;
    if(x<=a && b<=y){
      Lazy[node]+=val;
      propagate(a,b,node);
      return;
    }
    int mid=(a+b)/2;
    Update1(a,mid,2*node,x,y,val);
    Update1(mid+1,b,2*node+1,x,y,val);
  }
  
  lld Get(int a, int b, int node, int pos){
    propagate(a,b,node);
    if(pos<a || b<pos)return -1;
    //cout<<a<<" "<<b<<endl;
    if(a==b)return arr[a];
    int mid=(a+b)/2;
    return max(Get(a,mid,2*node,pos),Get(mid+1,b,2*node+1,pos));
  }
  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=Get(0,m,1,lo)+p[step];
    //cout<<V<<endl;
    /*rep(i,0,hi){
      arr[i]+=p[step];
    }*/
    Update1(0,m,1,0,lo,p[step]);
    rep(i,hi,m+1){
      
      arr[i]=max(Get(0,m,1,i),V+query(ST[ptr],0,m-1,lo,i-1));
    }
    /*rep(i,0,m+1)cout<<arr[i]<<" ";
      cout<<endl;*/
    step++;
  }
  
};
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->Get(0,m,1,m)<<endl;
  //cout<<query(ST,0,n-1,0,2)<<endl;
  return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:249: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:250: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:251: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]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9