oj.uz

Submission #137389

# Submission time Handle Problem Language Result Execution time Memory
137389 2019-07-27T14:50:54 Z KLPP Triple Jump (JOI19_jumps) C++14
100 / 100
 3384 ms 227452 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class ST{
  lld tree[4000000];
public:
  void build(int a, int b, int node){
    if(a==b){
      tree[node]=0;
      return;
    }
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
    tree[node]=max(tree[node*2],tree[node*2+1]);
  }
  void update(int a, int b, int node, int pos, lld val){
    if(pos<a || b<pos)return;
    if(a==b){
      tree[node]=val;
      return;
    }
    int mid=(a+b)/2;
    update(a,mid,2*node,pos,val);
    update(mid+1,b,2*node+1,pos,val);
    tree[node]=max(tree[node*2],tree[node*2+1]);
  }
  lld query(int a, int b, int node, int x, int y){
    if(x>y)return -100000000000;
    if(b<x || y<a)return -100000000000;
    if(x<=a && b<=y)return tree[node];
    int mid=(a+b)/2;
    return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
  }
};
class ST2{
  lld tree[4000000];
  lld lazy[4000000];
  lld Historic[4000000];
  lld Historic_lazy[1000000];
public:
  void build(int a, int b, int node){
    Historic_lazy[node]=0;
    lazy[node]=0;
    if(a==b){
      tree[node]=0;
      Historic[node]=0;
      return;
    }
    int mid=(a+b)/2;
    build(a,mid,2*node);
    build(mid+1,b,2*node+1);
    tree[node]=max(tree[2*node],tree[2*node+1]);
    Historic[node]=0;
    Historic[node]=max(Historic[node],tree[node]);
  }
  void propagate(int a, int b, int node){
    
    Historic[node]=max(Historic[node],tree[node]+Historic_lazy[node]);
    tree[node]+=lazy[node];
    if(a!=b){
      
      Historic_lazy[2*node]=max(Historic_lazy[2*node],lazy[2*node]+Historic_lazy[node]);
      lazy[2*node]+=lazy[node];
      
      Historic_lazy[2*node+1]=max(Historic_lazy[2*node+1],lazy[2*node+1]+Historic_lazy[node]);
      lazy[2*node+1]+=lazy[node];
    }
    lazy[node]=0;
    Historic_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;
      Historic_lazy[node]=max(lazy[node],Historic_lazy[node]);
      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);
    tree[node]=max(tree[2*node],tree[2*node+1]);
    Historic[node]=max(Historic[2*node],Historic[2*node+1]);
  }
  lld query(int a, int b, int node, int x, int y){
    propagate(a,b,node);
   
    if(y<a || b<x)return -1000000000;
    if(x<=a && b<=y)return Historic[node];
    int mid=(a+b)/2;
    return max(query(a,mid,2*node,x,y),query(mid+1,b,2*node+1,x,y));
  }
  void print(int a, int b, int node){
    cout<<a<<" "<<b<<" "<<tree[node]<<" "<<Historic[node]<<" "<<lazy[node]<<" "<<Historic_lazy[node]<<endl;
    if(a==b)return;
    int mid=(a+b)/2;
    print(a,mid,2*node);
    print(mid+1,b,2*node+1);
  }
};
int main(){
  srand(time(NULL));
  int n,q;
  scanf("%d",&n);
  lld arr[n];
  rep(i,0,n){

    scanf("%lld",&arr[i]);
    //arr[i]=rand()%100;
  }
  scanf("%d",&q);
  vector<pair<int,int> > Queries[n];
  rep(i,0,q){
    int l,r;
    scanf("%d %d",&l,&r);
    l--;r--;
    Queries[l].push_back(pair<int,int>(r,i));
  }
  ST *S=new ST();
  S->build(0,n-1,1);
  rep(i,0,n)S->update(0,n-1,1,i,arr[i]);
  set<int> candidates;
  vector<int> V[n];
  for(int i=n-1;i>-1;i--){
    queue<int> eliminate;
    for(set<int>::iterator it=candidates.begin();it!=candidates.end();it++){
      //cout<<a<<" "<<i<<" "<<S->query(0,n-1,1,i+1,a-1)<<endl;
      int a=*it;
      if(S->query(0,n-1,1,i+1,a-1)<min(arr[i],arr[a])){
	V[i].push_back(a);
      }
      if(S->query(0,n-1,1,i+1,a-1)>arr[i]){
	it=candidates.end();
	it--;
      }
      if(S->query(0,n-1,1,i+1,a-1)>arr[a]){
	eliminate.push(a);
      }
    }
    while(!eliminate.empty()){
      candidates.erase(eliminate.front());
      eliminate.pop();
    }
    /*trav(a,candidates){
      //cout<<a<<" "<<i<<" "<<S->query(0,n-1,1,i+1,a-1)<<endl;
      if(S->query(0,n-1,1,i+1,a-1)>=arr[a]){
	candidates.erase(a);
      }
    }*/
    
    //candidates.erase(candidates.begin(),candidates.upper_bound(arr[i]));
    candidates.insert(i);
    
  }
  ST2 *Tree=new ST2();
  Tree->build(0,n-1,1);
  rep(i,0,n){
    Tree->update(0,n-1,1,i,i,arr[i]);
  }
  //Tree->print(0,n-1,1);
  lld answers[q];
  for(int i=n-1;i>-1;i--){
    trav(a,V[i]){
      if(2*a-i<=n-1){
	//cout<<i<<" "<<a<<endl;
	Tree->update(0,n-1,1,2*a-i,n-1,arr[i]+arr[a]);
	//Tree->print(0,n-1,1);
	//cout<<endl;
	Tree->update(0,n-1,1,2*a-i,n-1,-(arr[i]+arr[a]));
	//Tree->print(0,n-1,1);
	//cout<<endl;
      }
    }
    trav(a,Queries[i]){
      answers[a.second]=Tree->query(0,n-1,1,i,a.first);
    }
  }
  rep(i,0,q){
    printf("%lld\n",answers[i]);
  }
  /*lld ans2=0;
  rep(i,0,n){
    rep(j,i+1,n){
      rep(k,2*j-i,n){
	ans2=max(ans2,arr[i]+arr[j]+arr[k]);
      }
    }
  }
  rep(i,0,n){
    rep(j,i+1,n){
      rep(k,2*j-i,n){
	if(arr[i]+arr[j]+arr[k]==ans2)cout<<i<<" "<<j<<" "<<k<<endl;
      }
    }
  }
  cout<<ans2<<endl;
  if(ans!=ans2){
    rep(i,0,n)cout<<arr[i]<<" ";
    cout<<endl;
  }*/
  return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
jumps.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&arr[i]);
     ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
   ~~~~~^~~~~~~~~
jumps.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&l,&r);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 133340 KB Output is correct
2 Correct 112 ms 133368 KB Output is correct
3 Correct 120 ms 133444 KB Output is correct
4 Correct 117 ms 133368 KB Output is correct
5 Correct 111 ms 133348 KB Output is correct
6 Correct 113 ms 133460 KB Output is correct
7 Correct 112 ms 133368 KB Output is correct
8 Correct 114 ms 133468 KB Output is correct
9 Correct 112 ms 133368 KB Output is correct
10 Correct 111 ms 133496 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 133340 KB Output is correct
2 Correct 112 ms 133368 KB Output is correct
3 Correct 120 ms 133444 KB Output is correct
4 Correct 117 ms 133368 KB Output is correct
5 Correct 111 ms 133348 KB Output is correct
6 Correct 113 ms 133460 KB Output is correct
7 Correct 112 ms 133368 KB Output is correct
8 Correct 114 ms 133468 KB Output is correct
9 Correct 112 ms 133368 KB Output is correct
10 Correct 111 ms 133496 KB Output is correct
11 Correct 590 ms 153592 KB Output is correct
12 Correct 580 ms 153696 KB Output is correct
13 Correct 582 ms 153700 KB Output is correct
14 Correct 587 ms 153680 KB Output is correct
15 Correct 586 ms 153848 KB Output is correct
16 Correct 627 ms 153080 KB Output is correct
17 Correct 595 ms 153080 KB Output is correct
18 Correct 590 ms 153116 KB Output is correct
19 Correct 613 ms 153632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 152732 KB Output is correct
2 Correct 638 ms 161912 KB Output is correct
3 Correct 577 ms 152492 KB Output is correct
4 Correct 943 ms 152824 KB Output is correct
5 Correct 932 ms 152668 KB Output is correct
6 Correct 964 ms 151928 KB Output is correct
7 Correct 927 ms 151992 KB Output is correct
8 Correct 942 ms 152028 KB Output is correct
9 Correct 941 ms 152284 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 133340 KB Output is correct
2 Correct 112 ms 133368 KB Output is correct
3 Correct 120 ms 133444 KB Output is correct
4 Correct 117 ms 133368 KB Output is correct
5 Correct 111 ms 133348 KB Output is correct
6 Correct 113 ms 133460 KB Output is correct
7 Correct 112 ms 133368 KB Output is correct
8 Correct 114 ms 133468 KB Output is correct
9 Correct 112 ms 133368 KB Output is correct
10 Correct 111 ms 133496 KB Output is correct
11 Correct 590 ms 153592 KB Output is correct
12 Correct 580 ms 153696 KB Output is correct
13 Correct 582 ms 153700 KB Output is correct
14 Correct 587 ms 153680 KB Output is correct
15 Correct 586 ms 153848 KB Output is correct
16 Correct 627 ms 153080 KB Output is correct
17 Correct 595 ms 153080 KB Output is correct
18 Correct 590 ms 153116 KB Output is correct
19 Correct 613 ms 153632 KB Output is correct
20 Correct 950 ms 152732 KB Output is correct
21 Correct 638 ms 161912 KB Output is correct
22 Correct 577 ms 152492 KB Output is correct
23 Correct 943 ms 152824 KB Output is correct
24 Correct 932 ms 152668 KB Output is correct
25 Correct 964 ms 151928 KB Output is correct
26 Correct 927 ms 151992 KB Output is correct
27 Correct 942 ms 152028 KB Output is correct
28 Correct 941 ms 152284 KB Output is correct
29 Correct 3359 ms 204880 KB Output is correct
30 Correct 2670 ms 227452 KB Output is correct
31 Correct 2403 ms 204088 KB Output is correct
32 Correct 3341 ms 204764 KB Output is correct
33 Correct 3339 ms 204428 KB Output is correct
34 Correct 3373 ms 203976 KB Output is correct
35 Correct 3384 ms 203772 KB Output is correct
36 Correct 3357 ms 203896 KB Output is correct
37 Correct 3367 ms 204476 KB Output is correct
38 Correct 2827 ms 210068 KB Output is correct
39 Correct 2821 ms 210236 KB Output is correct
40 Correct 2832 ms 208636 KB Output is correct
41 Correct 2859 ms 208248 KB Output is correct
42 Correct 2831 ms 208068 KB Output is correct
43 Correct 2831 ms 209004 KB Output is correct
44 Correct 2948 ms 209360 KB Output is correct
45 Correct 2917 ms 209632 KB Output is correct
46 Correct 2905 ms 207968 KB Output is correct
47 Correct 2930 ms 207736 KB Output is correct
48 Correct 2923 ms 207640 KB Output is correct
49 Correct 2906 ms 209040 KB Output is correct
50 Correct 3050 ms 207352 KB Output is correct
51 Correct 3066 ms 207256 KB Output is correct
52 Correct 3055 ms 206404 KB Output is correct
53 Correct 3106 ms 206272 KB Output is correct
54 Correct 3054 ms 206080 KB Output is correct
55 Correct 3053 ms 207812 KB Output is correct