fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long query(const vector<int> &values) {
  5.     long long answer = 0;
  6.     int N = values.size();
  7.  
  8.     vector<int> left(N+2), right(N+2);
  9.     for (int n=0; n<N+2; ++n) { left[n] = n+1; right[n] = n-1; }
  10.  
  11.     vector< pair<int,int> > events;
  12.     for (int n=0; n<N; ++n) events.push_back( { values[n], n+1 } );
  13.     sort( events.begin(), events.end() );
  14.  
  15.     for (const auto &ev : events) {
  16.         int le = left[ev.second-1], re = right[ev.second+1];
  17.         answer += 1LL * ev.first * (ev.second - le + 1) * (re - ev.second + 1);
  18.         right[le] = re; left[re] = le;
  19.     }
  20.     return answer;
  21. }
  22.  
  23. int main() {
  24.     int N, Q;
  25.     cin >> N >> Q;
  26.  
  27.     vector<int> A(N);
  28.     for (int &a : A) cin >> a;
  29.  
  30.     vector<int> D(N-1);
  31.     for (int n=0; n<N-1; ++n) D[n] = abs( A[n+1]-A[n] );
  32.  
  33.     while (Q--) {
  34.         int l, r; cin >> l >> r;
  35.         cout << query( vector<int>( D.begin()+l-1, D.begin()+r-1 ) ) << endl;
  36.     }
  37. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin 
10 4
1 5 2 9 1 3 4 2 1 7
2 4
3 8
7 10
1 9
stdout 
17
82
23
210
https://ideone.com/Lukj24
language:
C++14 (gcc 8.3)
created:
8 years 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!