fork download 
  1. #pragma GCC optimize("O3", "unroll-loops")
  2. // God Help me !!
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. // #define watch(x) cout << (#x) << " is " << (x) << endl
  6.  
  7. #define FILES freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
  8. #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  9. #define FIXED cout << fixed << setprecision(20)
  10. #define RANDOM srand(time(nullptr))
  11. #define int long long
  12. #define sz(a) (int)a.size()
  13. #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
  14. #define sep(i,a,b) for(int i=(int)a;i>=(int)b;i--)
  15. #define inf 0x3f3f3f3f
  16. #define pb push_back
  17. #define mp make_pair
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define all(a) a.begin(),a.end()
  21. #define x first
  22. #define y second
  23. #define endl "\n"
  24. #define n6 3000005
  25. #define n3 3005
  26. #define n5 300005
  27.  
  28. #define pi pair<int,int>
  29. #define pii pair<int,pi>
  30.  
  31. #define dbg1(x)                cout << #x << ": " << x << endl;
  32. #define dbg2(x, y)             cout << #x << ": " << x << " | " << #y << ": " << y << endl;
  33. #define dbg3(x, y, z)          cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  34. #define dbg4(a, b, c, d)       cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  35. #define dbg5(a, b, c, d, e)    cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  36. #define dbg6(a, b, c, d, e, f) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  37.  
  38. #define dbg(...) fprintf(stderr, __VA_ARGS__)
  39. #define dbgv(x) cout << #x << " = " << x << endl
  40. #define dbga(arr, len) {cout << #arr << " = "; for (int _ = 0; _ < len; _++)\
  41. cout << arr[_] << " "; cout << endl;}
  42. #define dbgi(it) {cout << #it << " = "; for (const auto& _ : it)\
  43. cout << _ << " "; cout << endl;}
  44.  
  45. const int md = (int) 1e9 + 7;
  46.  
  47. inline void add(int &a, int b) {
  48.   a += b;
  49.   if (a >= md) a -= md;
  50. }
  51.  
  52. inline void sub(int &a, int b) {
  53.   a -= b;
  54.   if (a < 0) a += md;
  55. }
  56.  
  57. inline int mul(int a, int b) {
  58.   return (int) ((long long) a * b % md);
  59. }
  60.  
  61. inline int power(int a, long long b) {
  62.   int res = 1;
  63.   while (b > 0) {
  64.     if (b & 1) {
  65.       res = mul(res, a);
  66.     }
  67.     a = mul(a, a);
  68.     b >>= 1;
  69.   }
  70.   return res;
  71. }
  72.  
  73.  
  74. void solve_util(int m, int &cnt, int &sum){
  75.  
  76.  
  77. }
  78.  
  79. const int K = 27;
  80. int st[n5][K];
  81. int st2[n5][K];
  82. int arr[n5];
  83. int N;
  84.  
  85. int logi[n5];
  86. void precompute_log(){
  87.     logi[1] = 0;
  88.     for (int i = 2; i <= n5; i++)
  89.         logi[i] = logi[i/2] + 1;
  90. }
  91.  
  92.  
  93. int range_sum(int L, int R){
  94.     long long sum = 0;
  95.     for (int j = K; j >= 0; j--) {
  96.         if ((1 << j) <= R - L + 1) {
  97.             sum += st[L][j];
  98.             L += 1 << j;
  99.         }
  100.     }
  101.     return sum;
  102. } 
  103.  
  104.  
  105. void RMQ(){  
  106.  
  107.     for (int i = 0; i < N; i++)
  108.         {
  109.             st[i][0] = arr[i];
  110.             st2[i][0] = arr[i];
  111.         }
  112.  
  113.     for (int j = 1; j <= K; j++)
  114.         for (int i = 0; i + (1 << j) <= N; i++){
  115.             st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
  116.             st2[i][j] = min(st2[i][j-1], st2[i + (1 << (j - 1))][j - 1]);
  117.         }
  118.  
  119. }
  120.  
  121. // int ans = 0;
  122. int RMQutil(int L, int R){
  123.  
  124.     int j = logi[R - L + 1];
  125.     int maxi = max(st[L][j], st[R - (1 << j) + 1][j]);
  126.     return maxi;
  127.  
  128. }
  129.  
  130. int RMQutil2(int L, int R){
  131.  
  132.     int j = logi[R - L + 1];
  133.     int maxi = min(st2[L][j], st2[R - (1 << j) + 1][j]);
  134.     return maxi;
  135. }
  136.  
  137. void solve(){
  138.     cin>>N;
  139.     int n =N; 
  140.     rep(i,0,n-1)cin>>arr[i];
  141.  
  142.     RMQ();
  143.     // dbga(arr,n);
  144.     int ans =0;
  145.     rep(i,0,n-1){
  146.         rep(j,i+1,n-1){
  147.             int maxi = RMQutil(i,j);
  148.             int mini = RMQutil2(i,j);
  149.             ans+=maxi-mini;
  150.         }
  151.     }
  152.  
  153.     cout<<ans<<endl;
  154. }
  155.  
  156. signed main()
  157. {
  158.     FAST; FIXED; RANDOM;
  159.     int t=1;
  160.     precompute_log();
  161.     // cin>>t;
  162.     // time_t time_t1, time_t2;
  163.     // time_t1 = clock();
  164.     while(t--)
  165.         solve();
  166.  
  167.     // time_t2 = clock();
  168.     // cout << "time taken :" << time_t2 - time_t1 << endl;
  169.     return 0;
  170. }
Success #stdin #stdout 0s 146496KB
comments (?)
stdin 
4
3
1
7
2
stdout 
31
https://ideone.com/TNKNl4
problem DIFERENC, based on SPOJ submission 22899655 (CPP14), 2018-12-18 09:17:51
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!