Submission #599504

---

Source Code Expand

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
 
using namespace std;
long long int A[100010];
long long int dp[100010][3];
const long long INF=1e18;
struct segtree{
  long long val[400005];
  int n;
  void init(int n_){
    n=1;
    while(n<n_) n<<=1;
    for(int i=0;i<2*n;++i) val[i]=-INF;
  }
  void set(int k,long long a){
    k+=n-1;
    val[k]=a;
    while(k){
      k=(k-1)/2;
      val[k]=max(val[k*2+1],val[k*2+2]);
    }
  }
  long long query(int a,int b,int i,int l,int r){
    if(a<=l && r<=b) return val[i];
    if(b<=l || r<=a) return -INF;
    int md=(l+r)>>1;
    return max(query(a,b,i*2+1,l,md),query(a,b,i*2+2,md,r));
  }
};

segtree hill,valley;

int zip[100005];
int main(){
  int N;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A[i];
    zip[i]=A[i];
  }
  sort(zip,zip+N);
  int zn=unique(zip,zip+N)-zip;
  for(int i=0;i<N;++i) A[i]=lower_bound(zip,zip+zn,A[i])-zip;

  long long ans=0;
  hill.init(zn);
  valley.init(zn);
  for(int i=0;i<N;i++){
    dp[i][0]=hill.query(A[i]+1,zn,0,0,hill.n)-zip[A[i]];//valley
    dp[i][1]=valley.query(0,A[i],0,0,valley.n)+zip[A[i]];//hill

    dp[i][0]=max(0ll,dp[i][0]);
    dp[i][1]=max(0ll,dp[i][1]);

    ans=max({ans,dp[i][0],dp[i][1]});

    hill.set(A[i],dp[i][1]+zip[A[i]]);
    valley.set(A[i],dp[i][0]-zip[A[i]]);
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result