fork download
copy 
  1. /*
  2.     Author: Cadocx
  3.     Codeforces: https://c...content-available-to-author-only...s.com/profile/Kadoc
  4.     VNOJ: oj.vnoi.info/user/Cadoc
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. // input/output
  11. #define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
  12. #define el cout << '\n'
  13. #define debug(x) cout << #x << " = " << x << '\n'
  14. #define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
  15. // #pragma GCC optimize("O2", "unroll-loops", "Ofast")
  16. // #pragma GCC target("avx,avx2,fma")
  17. //data type
  18. #define ll long long
  19. #define ull unsigned long long
  20. #define pii pair<int, int>
  21. #define pll pair<ll, ll>
  22. #define piv pair<int, vector<int>>
  23. #define vi vector<int>
  24. #define vl vector<ll>
  25. #define vc vector<char>
  26. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return 1; }; return 0; }
  27. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return 1; }; return 0; }
  28. //STL
  29. #define sz(x) (int)(x).size()
  30. #define FOR(i,l,r) for(auto i = l; i <= r; i++)
  31. #define FORD(i,r,l) for(auto i = r; i >= l; i--)
  32. #define forin(i,a) for(auto i : a)
  33. #define pb push_back
  34. #define eb emplace_back
  35. #define pf push_front
  36. #define all(x) (x).begin(), (x).end()
  37. #define fi first
  38. #define se second
  39. //bitmask
  40. #define bitcnt(n) __builtin_popcount(n)
  41. #define mask(i) (1 << (i))
  42. #define bit(n, i) (((n) >> (i)) & 1)
  43. #define set_on(n, i) ((n) | mask(i))
  44. #define set_off(n, i) ((n) & ~mask(i))
  45. //constant
  46. #define N 400005
  47. #define MOD 1000000007
  48. #define INF 0x3f3f3f3f
  49. #define LINF 0x3f3f3f3f3f3f3f3f
  50. #define base 31
  51. #define Kadoc 0
  52.  
  53. int n;
  54. int a[N];
  55. int lMax[N], rMax[N], lMin[N], rMin[N];
  56.  
  57. void solve(){
  58.     cin >> n;
  59.     FOR(i, 1, n) cin >> a[i];
  60.  
  61.     stack<int> s;
  62.     FOR(i, 1, n){
  63.         while(s.size() && a[s.top()] <= a[i]) s.pop();
  64.         lMax[i] = s.size()? s.top() + 1 : 1;
  65.         s.emplace(i);
  66.     }
  67.  
  68.     while(s.size()) s.pop();
  69.     FORD(i, n, 1){
  70.         while(s.size() && a[s.top()] < a[i]) s.pop();
  71.         rMax[i] = s.size()? s.top() - 1 : n;
  72.         s.emplace(i);
  73.     }
  74.  
  75.     while(s.size()) s.pop();
  76.     FOR(i, 1, n){
  77.         while(s.size() && a[s.top()] >= a[i]) s.pop();
  78.         lMin[i] = s.size()? s.top() + 1 : 1;
  79.         s.emplace(i);
  80.     }
  81.  
  82.     while(s.size()) s.pop();
  83.     FORD(i, n, 1){
  84.         while(s.size() && a[s.top()] > a[i]) s.pop();
  85.         rMin[i] = s.size()? s.top() - 1 : n;
  86.         s.emplace(i);
  87.     }
  88.  
  89.     ll Ans = 0;
  90.     FOR(i, 1, n) Ans += 1ll * a[i] * (i - lMax[i] + 1) * (rMax[i] - i + 1);
  91.     FOR(i, 1, n) Ans -= 1ll * a[i] * (i - lMin[i] + 1) * (rMin[i] - i + 1);
  92.  
  93.     cout << Ans;
  94. }
  95.  
  96. int main(){
  97.     #define NAME "TASK"
  98.     if(fopen(NAME".inp", "r")){
  99.         freopen(NAME".inp", "r", stdin);
  100.         freopen(NAME".out", "w", stdout);
  101.     }
  102.  
  103.     fastIO;
  104.  
  105.     if(Kadoc){
  106.         int tc; cin >> tc;
  107.         while(tc--){
  108.             solve();
  109.         }
  110.     } else solve();
  111. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qrf8e3
language:
C++14 (gcc 8.3)
created:
11 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!