fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define sti string
  5. #define bit(n,i) ((n>>i) &1)
  6. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  7. #define maxn 300005
  8. #define fi first
  9. #define se second
  10. #define int long long
  11.  
  12. using namespace std;
  13.  
  14. int dp[maxn],a[maxn];
  15. int st[4*maxn],lazy[4*maxn];
  16. int n,Lefttt,Rightttt;
  17. const int INF = 4e18;
  18.  
  19. void apply(int id,int val){
  20.     st[id] += val;
  21.     lazy[id] += val;
  22. }
  23.  
  24. void down(int id){
  25.     if(lazy[id] == 0) return;
  26.     apply(id*2,lazy[id]);
  27.     apply(id*2+1,lazy[id]);
  28.     lazy[id] = 0;
  29. }
  30.  
  31. void update(int id,int l,int r,int u,int v,int val){
  32.     if(l>r || u>v || l>v || r<u) return;
  33.     if(u<=l && r<=v){
  34.         apply(id,val);
  35.         return;
  36.     }
  37.     int mid = (l+r)/2;
  38.     down(id);
  39.     update(id*2,l,mid,u,v,val);
  40.     update(id*2+1,mid+1,r,u,v,val);
  41.     st[id] = min(st[id*2],st[id*2+1]);
  42. }
  43.  
  44. void build(int id,int l,int r){
  45.     lazy[id] = 0;
  46.     if(l==r){
  47.         st[id] = (l==0 ? 0 : INF);
  48.         return;
  49.     }
  50.     int mid = (l+r)/2;
  51.     build(id*2,l,mid);
  52.     build(id*2+1,mid+1,r);
  53.     st[id] = min(st[id*2],st[id*2+1]);
  54. }
  55.  
  56. int get(int id,int l,int r,int u,int v){
  57.     if(l>r || u>v || l>v || r<u) return INF;
  58.     if(u<=l && r<=v) return st[id];
  59.     down(id);
  60.     int mid = (l+r)/2;
  61.     return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
  62. }
  63.  
  64. void setval(int id,int l,int r,int pos,int val){
  65.     if(l==r){
  66.         st[id] = val;
  67.         lazy[id] = 0;
  68.         return;
  69.     }
  70.     int mid = (l+r)/2;
  71.     down(id);
  72.     if(pos<=mid) setval(id*2,l,mid,pos,val);
  73.     else setval(id*2+1,mid+1,r,pos,val);
  74.     st[id] = min(st[id*2],st[id*2+1]);
  75. }
  76.  
  77. signed main(){
  78.     itachi
  79.     freopen("FORMAT.inp","r",stdin);
  80.     freopen("FORMAT.out","w",stdout);
  81.     cin>>n>>Lefttt>>Rightttt;
  82.     for(int i=1;i<=n;i++) cin>>a[i];
  83.     for(int i=0;i<=n;i++) dp[i] = INF;
  84.     build(1,0,n);
  85.     vector<pair<int,int>> stMax,stMin;
  86.     for(int i=1;i<=n;i++){
  87.         int last = i;
  88.         while(!stMax.empty() && stMax.back().fi<=a[i]){
  89.             int val = stMax.back().fi;
  90.             int L = stMax.back().se;
  91.             stMax.pop_back();
  92.             if(L-1<=last-2) update(1,0,n,L-1,last-2,a[i]-val);
  93.             last = L;
  94.         }
  95.         update(1,0,n,i-1,i-1,a[i]);
  96.         stMax.push_back({a[i],last});
  97.         last = i;
  98.         while(!stMin.empty() && stMin.back().fi>a[i]){
  99.             int val = stMin.back().fi;
  100.             int L = stMin.back().se;
  101.             stMin.pop_back();
  102.             if(L-1<=last-2) update(1,0,n,L-1,last-2,val-a[i]);
  103.             last = L;
  104.         }
  105.         update(1,0,n,i-1,i-1,-a[i]);
  106.         stMin.push_back({a[i],last});
  107.         dp[i] = INF;
  108.         if(i - Lefttt >= 0){
  109.             int Left = max(0LL, i - Rightttt);
  110.             int Right = i - Lefttt;
  111.             dp[i] = get(1,0,n,Left,Right);
  112.             if(dp[i] >= INF/2) dp[i] = INF;
  113.         }
  114.         setval(1,0,n,i,dp[i]);
  115.     }
  116.     cout<<(dp[n]>=INF ? -1 : dp[n]);
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0.01s 8016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mljIOi
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!