oj.uz

Submission #120198

# Submission time Handle Problem Language Result Execution time Memory
120198 2019-06-23T18:08:24 Z KLPP Two Dishes (JOI19_dishes) C++14
10 / 100
 10000 ms 299216 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10107 ms 211944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 157044 KB Output is correct
2 Correct 118 ms 156920 KB Output is correct
3 Correct 119 ms 156892 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 120 ms 156920 KB Output is correct
6 Correct 120 ms 156920 KB Output is correct
7 Correct 121 ms 157032 KB Output is correct
8 Correct 119 ms 156920 KB Output is correct
9 Correct 120 ms 156924 KB Output is correct
10 Correct 119 ms 156920 KB Output is correct
11 Correct 124 ms 156920 KB Output is correct
12 Correct 126 ms 156920 KB Output is correct
13 Correct 125 ms 157020 KB Output is correct
14 Correct 120 ms 156888 KB Output is correct
15 Correct 119 ms 156920 KB Output is correct
16 Correct 122 ms 156876 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 157044 KB Output is correct
2 Correct 118 ms 156920 KB Output is correct
3 Correct 119 ms 156892 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 120 ms 156920 KB Output is correct
6 Correct 120 ms 156920 KB Output is correct
7 Correct 121 ms 157032 KB Output is correct
8 Correct 119 ms 156920 KB Output is correct
9 Correct 120 ms 156924 KB Output is correct
10 Correct 119 ms 156920 KB Output is correct
11 Correct 124 ms 156920 KB Output is correct
12 Correct 126 ms 156920 KB Output is correct
13 Correct 125 ms 157020 KB Output is correct
14 Correct 120 ms 156888 KB Output is correct
15 Correct 119 ms 156920 KB Output is correct
16 Correct 122 ms 156876 KB Output is correct
17 Correct 948 ms 158084 KB Output is correct
18 Correct 130 ms 158712 KB Output is correct
19 Correct 586 ms 158840 KB Output is correct
20 Correct 331 ms 158584 KB Output is correct
21 Correct 311 ms 158500 KB Output is correct
22 Correct 615 ms 158608 KB Output is correct
23 Correct 585 ms 158740 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 157044 KB Output is correct
2 Correct 118 ms 156920 KB Output is correct
3 Correct 119 ms 156892 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 120 ms 156920 KB Output is correct
6 Correct 120 ms 156920 KB Output is correct
7 Correct 121 ms 157032 KB Output is correct
8 Correct 119 ms 156920 KB Output is correct
9 Correct 120 ms 156924 KB Output is correct
10 Correct 119 ms 156920 KB Output is correct
11 Correct 124 ms 156920 KB Output is correct
12 Correct 126 ms 156920 KB Output is correct
13 Correct 125 ms 157020 KB Output is correct
14 Correct 120 ms 156888 KB Output is correct
15 Correct 119 ms 156920 KB Output is correct
16 Correct 122 ms 156876 KB Output is correct
17 Correct 948 ms 158084 KB Output is correct
18 Correct 130 ms 158712 KB Output is correct
19 Correct 586 ms 158840 KB Output is correct
20 Correct 331 ms 158584 KB Output is correct
21 Correct 311 ms 158500 KB Output is correct
22 Correct 615 ms 158608 KB Output is correct
23 Correct 585 ms 158740 KB Output is correct
24 Execution timed out 10098 ms 299216 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 157044 KB Output is correct
2 Correct 118 ms 156920 KB Output is correct
3 Correct 119 ms 156892 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 120 ms 156920 KB Output is correct
6 Correct 120 ms 156920 KB Output is correct
7 Correct 121 ms 157032 KB Output is correct
8 Correct 119 ms 156920 KB Output is correct
9 Correct 120 ms 156924 KB Output is correct
10 Correct 119 ms 156920 KB Output is correct
11 Correct 124 ms 156920 KB Output is correct
12 Correct 126 ms 156920 KB Output is correct
13 Correct 125 ms 157020 KB Output is correct
14 Correct 120 ms 156888 KB Output is correct
15 Correct 119 ms 156920 KB Output is correct
16 Correct 122 ms 156876 KB Output is correct
17 Correct 948 ms 158084 KB Output is correct
18 Correct 130 ms 158712 KB Output is correct
19 Correct 586 ms 158840 KB Output is correct
20 Correct 331 ms 158584 KB Output is correct
21 Correct 311 ms 158500 KB Output is correct
22 Correct 615 ms 158608 KB Output is correct
23 Correct 585 ms 158740 KB Output is correct
24 Execution timed out 10098 ms 299216 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 157044 KB Output is correct
2 Correct 118 ms 156920 KB Output is correct
3 Correct 119 ms 156892 KB Output is correct
4 Correct 122 ms 156920 KB Output is correct
5 Correct 120 ms 156920 KB Output is correct
6 Correct 120 ms 156920 KB Output is correct
7 Correct 121 ms 157032 KB Output is correct
8 Correct 119 ms 156920 KB Output is correct
9 Correct 120 ms 156924 KB Output is correct
10 Correct 119 ms 156920 KB Output is correct
11 Correct 124 ms 156920 KB Output is correct
12 Correct 126 ms 156920 KB Output is correct
13 Correct 125 ms 157020 KB Output is correct
14 Correct 120 ms 156888 KB Output is correct
15 Correct 119 ms 156920 KB Output is correct
16 Correct 122 ms 156876 KB Output is correct
17 Correct 948 ms 158084 KB Output is correct
18 Correct 130 ms 158712 KB Output is correct
19 Correct 586 ms 158840 KB Output is correct
20 Correct 331 ms 158584 KB Output is correct
21 Correct 311 ms 158500 KB Output is correct
22 Correct 615 ms 158608 KB Output is correct
23 Correct 585 ms 158740 KB Output is correct
24 Execution timed out 10098 ms 299216 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10107 ms 211944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10107 ms 211944 KB Time limit exceeded
2 Halted 0 ms 0 KB -