fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 5e5 + 5, mod = 1e9;
  4. struct node {
  5.     int sm, sM, sL, smM, sML, smL, smML;
  6. };
  7. node operator+(node a, node b) {
  8.     node c = {a.sm + b.sm,   a.sM + b.sM,   a.sL + b.sL,    a.smM + b.smM,
  9.               a.sML + b.sML, a.smL + b.smL, a.smML + b.smML};
  10.     return c;
  11. }
  12. struct LZ {
  13.     int m, M, l;
  14. };
  15. node t[4 * N];
  16. LZ lz[4 * N];
  17. void downl(int id, int l, int r) {
  18.     t[id].sL += 1ll * (lz[id].l * (r - l + 1)) % mod;
  19.     t[id].sL %= mod;
  20.     t[id].smL += 1ll * t[id].sm * lz[id].l % mod;
  21.     t[id].smL %= mod;
  22.     t[id].smML += 1ll * t[id].smM * lz[id].l % mod;
  23.     if (l != r) {
  24.         lz[id * 2].l += lz[id].l;
  25.         lz[id * 2 + 1].l += lz[id].l;
  26.         lz[id * 2].l %= mod;
  27.         lz[id * 2 + 1].l %= mod;
  28.     }
  29.     lz[id].l = 0;
  30. }
  31. void downm(int id, int l, int r) {
  32.     t[id].sm += 1ll * lz[id].m * (r - l + 1) % mod;
  33.     t[id].sm %= mod;
  34.     t[id].smM += 1ll * t[id].sM * lz[id].m % mod;
  35.     t[id].smM %= mod;
  36.     t[id].smML += 1ll * t[id].sML * lz[id].m % mod;
  37.     t[id].smML %= mod;
  38.     if (l != r) {
  39.         lz[id * 2].m = lz[id].m;
  40.         lz[id * 2 + 1].m = lz[id].m;
  41.     }
  42.     lz[id].m = 0;
  43. }
  44. void downM(int id, int l, int r) {
  45.     t[id].sM += 1ll * lz[id].M * (r - l + 1) % mod;
  46.     t[id].sM %= mod;
  47.     t[id].smM += 1ll * t[id].sM * lz[id].M % mod;
  48.     t[id].sm %= mod;
  49.     t[id].smML += 1ll * t[id].smL * lz[id].M % mod;
  50.     t[id].smML %= mod;
  51.     lz[id].M = 0;
  52. }
  53. void down(int id, int l, int r) {
  54.     downl(id, l, r);
  55.     if (lz[id].m != 0) downm(id, l, r);
  56.     if (lz[id].M != 0) downM(id, l, r);
  57. }
  58. void updatel(int id, int l, int r, int u, int v, int x) {
  59.     down(id, l, r);
  60.     if (r < u || v < l) return;
  61.     if (u <= l && r <= v) {
  62.         lz[id].l += x;
  63.         down(id, l, r);
  64.         return;
  65.     }
  66.     updatel(id * 2, l, (l + r) / 2, u, v, x);
  67.     updatel(id * 2 + 1, (l + r) / 2 + 1, r, u, v, x);
  68.     t[id] = t[id * 2] + t[id * 2 + 1];
  69. }
  70. void updatem(int id, int l, int r, int u, int v, int x) {
  71.     down(id, l, r);
  72.     if (r < u || v < l) return;
  73.     if (u <= l && r <= v) {
  74.         lz[id].m = x;
  75.         down(id, l, r);
  76.         return;
  77.     }
  78.     updatem(id * 2, l, (l + r) / 2, u, v, x);
  79.     updatem(id * 2 + 1, (l + r) / 2 + 1, r, u, v, x);
  80.     t[id] = t[id * 2] + t[id * 2 + 1];
  81. }
  82. void updateM(int id, int l, int r, int u, int v, int x) {
  83.     down(id, l, r);
  84.     if (r < u || v < l) return;
  85.     if (u <= l && r <= v) {
  86.         lz[id].M = x;
  87.         down(id, l, r);
  88.         return;
  89.     }
  90.     updateM(id * 2, l, (l + r) / 2, u, v, x);
  91.     updateM(id * 2 + 1, (l + r) / 2 + 1, r, u, v, x);
  92.     t[id] = t[id * 2] + t[id * 2 + 1];
  93. }
  94. int get(int id, int l, int r, int u, int v) {
  95.     down(id, l, r);
  96.     if (r < u || v < l) return 0;
  97.     if (u <= l && r <= v) return t[id].smML;
  98.     return (get(id * 2, l, (l + r) / 2, u, v) +
  99.             get(id * 2 + 1, (l + r) / 2 + 1, r, u, v)) %
  100.            mod;
  101. }
  102. int a[N];
  103. signed main() {
  104.     int n, pm, pM;
  105.     cin >> n;
  106.     for (int i = 1; i <= n; i++) cin >> a[i];
  107.     stack<int> sm, sM;
  108.     int res = 0;
  109.     for (int i = 1; i <= n; i++) {
  110.         while (sm.size() && a[sm.top()] <= a[i]) sm.pop();
  111.         if (sm.empty())
  112.             pm = i;
  113.         else
  114.             pm = sm.top();
  115.         sm.push(i);
  116.         while (sM.size() && a[sM.top()] >= a[i]) sM.pop();
  117.         if (sM.empty())
  118.             pM = i;
  119.         else
  120.             pM = sM.top();
  121.         sM.push(i);
  122.         updatel(1, 1, n, 1, i, 1);
  123.         updatem(1, 1, n, pm, i, a[i]);
  124.         updateM(1, 1, n, pM, i, a[i]);
  125.         res += get(1, 1, n, 1, i);
  126.         res %= mod;
  127.     }
  128.     cout << res;
  129. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pkNtrN
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!