fork download 
  1. /* ___________________________________________ */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6. #define int long long 
  7. #define fi first
  8. #define se second
  9. #define pushb push_back
  10. #define SZ(v) (int)v.size()
  11. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  12. #define debug cout << "NO ERROR"; exit(0);
  13. #define endl "\n"
  14. #define mapa(x, y) make_pair(x, y)
  15. #define double long double
  16. #define lb lower_bound
  17. #define ub upper_bound
  18. #define pii pair<int, int>
  19. #define ALL(v) v.begin(), v.end()
  20. #define BIT(x, i) (((x) >> (i)) & 1)
  21.  
  22. template<class X, class Y>
  23. bool minimize(X &x, const Y &y) {
  24.     if (x > y) {
  25.         x = y;
  26.         return true;
  27.     }
  28.     return false;
  29. }
  30.  
  31. template<class X, class Y>
  32. bool maximize(X &x, const Y &y) {
  33.     if (x < y) {
  34.         x = y;
  35.         return true;
  36.     }
  37.     return false;
  38. }
  39.  
  40. int lcm(int x, int y){
  41.     return x / __gcd(x, y) * y;
  42. }
  43.  
  44. const int INF = 1e18;
  45. const double pi = acos(-1);
  46. const int MOD = 1e9 + 7;
  47. const int LimN = 3e3 + 5;
  48. const int LimM = 1e5 + 5;
  49. const double dist = 0.000001;
  50. const int ADD = 96e3;
  51.  
  52. const int d4x[4] = {-1, 1, 0, 0};
  53. const int d4y[4] = {0, 0, 1, -1};
  54.  
  55. int a[LimN];
  56. int cost[LimN][LimN];
  57.  
  58.  
  59. class SegmentTree {
  60.  
  61. private:
  62.     int n;
  63.     vector<int> v;
  64.  
  65.     void update(int id, int l, int r, int pos, int val) {
  66.         if (pos < l || pos > r) return;
  67.  
  68.         if (l == r) {
  69.             v[id] = val;
  70.             return;
  71.         }
  72.  
  73.         int mid = (l + r) / 2;
  74.  
  75.         update(id * 2, l, mid, pos, val);
  76.         update(id * 2 + 1, mid + 1, r, pos, val);
  77.  
  78.         v[id] = min(v[id * 2], v[id * 2 + 1]);
  79.     }
  80.  
  81.     int get(int id, int l, int r, int sta, int fin) {
  82.         if (fin < l || r < sta) return INF;
  83.  
  84.         if (sta <= l && r <= fin) {
  85.             return v[id];
  86.         }
  87.  
  88.         int mid = (l + r) / 2;
  89.  
  90.         return min(
  91.             get(id * 2, l, mid, sta, fin),
  92.             get(id * 2 + 1, mid + 1, r, sta, fin)
  93.         );
  94.     }
  95.  
  96. public:
  97.     SegmentTree(int _n) {
  98.         n = _n;
  99.         v.assign(n * 5 + 5, INF);
  100.     }
  101.  
  102.     void update(int pos, int val) {
  103.         update(1, 1, n, pos, val);
  104.     }
  105.  
  106.     int get(int sta, int fin) {
  107.         return get(1, 1, n, sta, fin);
  108.     }
  109. };
  110.  
  111.  
  112.  
  113. class SegmentTree2 {
  114.  
  115. private:
  116.     int n;
  117.     vector<int> v;
  118.  
  119.     void update(int id, int l, int r, int pos, int val) {
  120.         if (pos < l || pos > r) return;
  121.  
  122.         if (l == r) {
  123.             v[id] = val;
  124.             return;
  125.         }
  126.  
  127.         int mid = (l + r) / 2;
  128.  
  129.         update(id * 2, l, mid, pos, val);
  130.         update(id * 2 + 1, mid + 1, r, pos, val);
  131.  
  132.         v[id] = max(v[id * 2], v[id * 2 + 1]);
  133.     }
  134.  
  135.     int get(int id, int l, int r, int sta, int fin) {
  136.         if (fin < l || r < sta) return -INF;
  137.  
  138.         if (sta <= l && r <= fin) {
  139.             return v[id];
  140.         }
  141.  
  142.         int mid = (l + r) / 2;
  143.  
  144.         return max(
  145.             get(id * 2, l, mid, sta, fin),
  146.             get(id * 2 + 1, mid + 1, r, sta, fin)
  147.         );
  148.     }
  149.  
  150. public:
  151.     SegmentTree2(int _n) {
  152.         n = _n;
  153.         v.assign(n * 5 + 5, -INF);
  154.     }
  155.  
  156.     void update(int pos, int val) {
  157.         update(1, 1, n, pos, val);
  158.     }
  159.  
  160.     int get(int sta, int fin) {
  161.         return get(1, 1, n, sta, fin);
  162.     }
  163. };
  164.  
  165. void solve() {
  166.  
  167.     int n;
  168.     cin >> n;
  169.  
  170.     SegmentTree IT(n);
  171.     SegmentTree2 IT2(n);
  172.  
  173.     for (int i = 1; i <= n; i ++) {
  174.         cin >> a[i];
  175.         IT.update(i, a[i]);
  176.         IT2.update(i, a[i]);
  177.     }  
  178.  
  179.  
  180.  
  181.     int ans = 0;
  182.     for (int i = 1; i <= n; i ++) {
  183.         for (int j = i; j <= n; j ++) {
  184.             int l = IT.get(i, j);
  185.             int r = IT2.get(i, j);
  186.  
  187.             //cout << i << " " << j << " " << abs(r - l) << endl;
  188.  
  189.             ans += abs(r - l);
  190.         }
  191.  
  192.     }
  193.  
  194.     cout << ans;
  195.  
  196. }
  197.  
  198. /* Authors: nguyen Hai Duong from le Do secondary school Da nang */
  199.  
  200. signed main() {
  201.     #ifndef ONLINE_JUDGE
  202.     freopen("ab.inp", "r", stdin);
  203.     freopen("ab.out", "w", stdout);
  204.     #else
  205.     // freopen("task.inp", "r", stdin);
  206.     // freopen("task.out", "w", stdout);
  207.     #endif
  208.  
  209.     fast;
  210.  
  211.     int numtest = 1;
  212.     // cin >> numtest;
  213.  
  214.     while (numtest--) {
  215.         solve();
  216.     }
  217.  
  218.     return 0;
  219. }
  220.  
  221. // THIS IS DUONG's TEMPLATE &&09042012&&
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BEIGMt
language:
C++14 (clang 8.0)
created:
4 days 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!