oj.uz

Submission #137237

# Submission time Handle Problem Language Result Execution time Memory
137237 2019-07-27T09:39:01 Z KLPP Triple Jump (JOI19_jumps) C++14
0 / 100
 226 ms 45648 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));
  }

};
int main(){
  int n,q;
  scanf("%d",&n);
  lld arr[n];
  rep(i,0,n)scanf("%lld",&arr[i]);
  //scanf("%d",&q);
  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--){
    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)<min(arr[i],arr[a])){
	V[i].push_back(a);
      }
    }
    candidates.clear();
    candidates.insert(i);
    trav(a,V[i])candidates.insert(a);
  }
  lld ans=0;
  rep(i,0,n){
    trav(a,V[i]){
      //cout<<a<<" ";
      ans=max(ans,arr[i]+arr[a]+S->query(0,n-1,1,2*a-i,n-1));
    }//cout<<endl;
  }
  cout<<ans<<endl;
  
  
  return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:41:9: warning: unused variable 'q' [-Wunused-variable]
   int n,q;
         ^
jumps.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
jumps.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   rep(i,0,n)scanf("%lld",&arr[i]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Incorrect 28 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Incorrect 28 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 45648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Incorrect 28 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -