fork download
copy 
  1. /* Authors: Vu Hoang Bach from Phuoc Hoa Secondary School */
  2. /* Enjoy TheFatRat's music while reading my code. Link: https://w...content-available-to-author-only...e.com/watch?v=GCx9FU59FJc&t=669s */
  3.  
  4. //#pragma GCC optimize("O3", "unroll-loops")
  5. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  6.  
  7. #include <bits/stdc++.h>
  8. #define ldb long double
  9. //#define double ldb
  10. #define db double
  11. #define name "test"
  12. #define unomap unordered_map
  13. #define unoset unordered_set
  14. #define endl '\n'
  15. #define str string
  16. #define strstr stringstream
  17. #define sz(a) a.size()
  18. #define ll long long
  19. //#define int ll
  20. #define pii pair <int, int>
  21. #define pll pair <ll, ll>
  22. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  23. #define ull unsigned ll
  24. #define fir first
  25. #define sec second
  26. #define idc cin.ignore()
  27. #define lb lower_bound
  28. #define ub upper_bound
  29. #define all(s) s.begin(), s.end()
  30. #define rev reverse
  31. #define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  32. #define skibidi int main
  33. #define rizz signed main
  34. #define gcd __gcd
  35. #define found(a, mp) mp.find(a) != mp.end()
  36. #define game_over exit(0);
  37. #define stfu return 0;
  38. #define stop break;
  39. #define odd(n) n & 1
  40. #define pushb push_back
  41. #define popb pop_back
  42. #define pushf push_front
  43. #define popf pop_front
  44. #define even(n) !odd(n)
  45. #define mul2x(a, x) a << x
  46. #define div2x(a, x) a >> x
  47. #define no_check continue;
  48. #define lcm(a, b) a / __gcd(a, b) * b
  49. #define log_base(x, base) log(x) / log(base)
  50. #define debug clog << "No errors!"; game_over;
  51. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  52. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  53. #define fors(i, a, b) for (int i = a; i >= b; --i)
  54. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  55. #define meme memset
  56. #define pqueue priority_queue
  57. #define want(x) cout << fixed << setprecision(x);
  58. #define excuting_time cout << "Excuting time: " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms";
  59. using namespace std;
  60. const int MOD = 1e9 + 7; // 998244353
  61. const int inf = 1e9;
  62. const ll INF = 1e18;
  63. const int N = 4e5;
  64.  
  65. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  66. ll random(const ll &L, const ll &R)
  67. {
  68.     return uniform_int_distribution<ll> (L, R) (rng);
  69. }
  70.  
  71. int n, a[N + 5];
  72. stack <int> st;
  73. ll res, res_mn, res_mx, PLS[N + 5], PGS[N + 5], NLE[N + 5], NGE[N + 5];
  74.  
  75. void clear_st()
  76. {
  77.     while (!st.empty()) st.pop();
  78. }
  79.  
  80. void cook()
  81. {
  82.     cin >> n;
  83.     forw (i, 1, n) cin >> a[i];
  84.     res = res_mn = res_mx = 0;
  85.  
  86.     clear_st();
  87.     a[0] = -inf - 1;
  88.     st.push(0);
  89.     forw (i, 1, n)
  90.     {
  91.         while (a[st.top()] >= a[i]) st.pop();
  92.         PLS[i] = st.top();
  93.         st.push(i);
  94.     }
  95.  
  96.     clear_st();
  97.     a[0] = inf + 1;
  98.     st.push(0);
  99.     forw (i, 1, n)
  100.     {
  101.         while (a[st.top()] <= a[i]) st.pop();
  102.         PGS[i] = st.top();
  103.         st.push(i);
  104.     }
  105.  
  106.     clear_st();
  107.     a[n + 1] = -inf - 1;
  108.     st.push(n + 1);
  109.     fors (i, n, 1)
  110.     {
  111.         while (a[st.top()] > a[i]) st.pop();
  112.         NLE[i] = st.top();
  113.         st.push(i);
  114.     }
  115.  
  116.     clear_st();
  117.     a[n + 1] = inf + 1;
  118.     st.push(n + 1);
  119.     fors (i, n, 1)
  120.     {
  121.         while (a[st.top()] < a[i]) st.pop();
  122.         NGE[i] = st.top();
  123.         st.push(i);
  124.     }
  125.  
  126.     forw (i, 1, n)
  127.         res_mn += a[i] * (i - NLE[i]) * (PLS[i] - i);
  128.     forw (i, 1, n)
  129.         res_mx += a[i] * (i - NGE[i]) * (PGS[i] - i);
  130.     res = res_mx - res_mn;
  131.     cout << res << endl;
  132. }
  133.  
  134. skibidi()
  135. //rizz()
  136. {
  137.     srand(time(NULL));
  138.     sigma;
  139.     /*
  140.     if (fopen(name".INP", "r"))
  141.     {
  142.         freopen(name".INP", "r", stdin);
  143.         freopen(name".OUT", "w", stdout);
  144.     }
  145.     */
  146.     int numTest = 1;
  147. //    cin >> numTest;
  148.     while (numTest--)
  149.     {
  150.         cook();
  151.     }
  152.     stfu;
  153. }
  154.  
Success #stdin #stdout 0.01s 11712KB
comments (?)
stdin
copy 
4
3 1 7 2
stdout
copy 
31
https://ideone.com/OuRLA7
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!