fork download
copy 
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <deque>
  7. #include <set>
  8. #include <map>
  9. #include <assert.h>
  10. #include <math.h>
  11.  
  12. #define ll long long
  13. #define ld long double
  14. #define fi first
  15. #define se second
  16. #define sz(a) (int)a.size()
  17.  
  18. using namespace std;
  19.  
  20. inline void setmin(int &x, int y) { if (y < x) x = y; }
  21. inline void setmax(int &x, int y) { if (y > x) x = y; }
  22. inline void setmin(ll &x, ll y) { if (y < x) x = y; }
  23. inline void setmax(ll &x, ll y) { if (y > x) x = y; }
  24.  
  25. const int N = 500000;
  26. const int inf = (int)1e9 + 1;
  27. const int MOD = (int)1e9 + 7;
  28. const ld pi = atan2(0, -1);
  29.  
  30. int a[N];
  31.  
  32. int max_l[N], max_r[N];
  33.  
  34. void calc_max_to(int n)
  35. {
  36.     int cur = -1, pos = 0;
  37.     deque<pair<int, int> > q;
  38.     for (int i = 0; i < n; i++)
  39.     {
  40.         while (sz(q) > 0 && a[i] <= q.back().fi)
  41.             q.pop_back();
  42.         q.push_back({a[i], i});
  43.         setmin(pos, sz(q) - 1);
  44.         while (cur + 1 <= i)
  45.         {
  46.             if (q[pos].se > cur)
  47.             {
  48.                 if ((i - (cur + 1) + 1) >= q[pos].fi)
  49.                     cur++;
  50.                 else
  51.                     break;
  52.             }
  53.             else
  54.             {
  55.                 if (pos + 1 < sz(q) && (i - (cur + 1) + 1) >= q[pos + 1].fi)
  56.                 {
  57.                     cur++;
  58.                     pos++;
  59.                 }
  60.                 else
  61.                     break;
  62.             }
  63.         }
  64.         max_l[i] = cur;
  65.     }
  66. }
  67.  
  68. int to_l[N], to_r[N];
  69.  
  70. int cnt_v;
  71. int tree[1100000], add[1100000];
  72.  
  73. void build(int n)
  74. {
  75.     cnt_v = 1;
  76.     while (cnt_v < n)
  77.         cnt_v <<= 1;
  78.     fill(tree, tree + cnt_v * 2 - 1, 0);
  79. }
  80.  
  81. void push(int x, int lx, int rx)
  82. {
  83.     if (add[x] == 0)
  84.         return;
  85.     int len = (rx - lx) >> 1;
  86.     tree[(x << 1) + 1] = (tree[(x << 1) + 1] + 1LL * add[x] * len) % MOD;
  87.     add[(x << 1) + 1] += add[x];
  88.     if (add[(x << 1) + 1] >= MOD)
  89.         add[(x << 1) + 1] -= MOD;
  90.     tree[(x << 1) + 2] = (tree[(x << 1) + 2] + 1LL * add[x] * len) % MOD;
  91.     add[(x << 1) + 2] += add[x];
  92.     if (add[(x << 1) + 2] >= MOD)
  93.         add[(x << 1) + 2] -= MOD;
  94.     add[x] = 0;
  95. }
  96.  
  97. void upd(int x, int lx, int rx, int l, int r, int v)
  98. {
  99.     if (lx >= r || l >= rx)
  100.         return;
  101.     else if (lx >= l && rx <= r)
  102.     {
  103.         tree[x] = (tree[x] + 1LL * v * (rx - lx)) % MOD;
  104.         add[x] += v;
  105.         if (add[x] >= MOD)
  106.             add[x] -= MOD;
  107.     }
  108.     else
  109.     {
  110.         push(x, lx, rx);
  111.         upd((x << 1) + 1, lx, (lx + rx) >> 1, l, r, v);
  112.         upd((x << 1) + 2, (lx + rx) >> 1, rx, l, r, v);
  113.         tree[x] = tree[(x << 1) + 1] + tree[(x << 1) + 2];
  114.         if (tree[x] >= MOD)
  115.             tree[x] -= MOD;
  116.     }
  117. }
  118.  
  119. int get(int x, int lx, int rx, int l, int r)
  120. {
  121.     if (lx >= r || l >= rx)
  122.         return 0;
  123.     else if (lx >= l && rx <= r)
  124.         return tree[x];
  125.     else
  126.     {
  127.         push(x, lx, rx);
  128.         int res = get((x << 1) + 1, lx, (lx + rx) >> 1, l, r) + get((x << 1) + 2, (lx + rx) >> 1, rx, l, r);
  129.         if (res >= MOD)
  130.             res -= MOD;
  131.         return res;
  132.     }
  133. }
  134.  
  135. int main()
  136. {
  137.     //freopen("a.in", "r", stdin);
  138.     //freopen("a.out", "w", stdout);
  139.     ios_base::sync_with_stdio(0);
  140.     cin.tie(0);
  141.     cout.precision(20);
  142.     cout << fixed;
  143.     //ll TL = 0.95 * CLOCKS_PER_SEC;
  144.     //clock_t time = clock();
  145.     int n;
  146.     cin >> n;
  147.     for (int i = 0; i < n; i++)
  148.         cin >> a[i];
  149.  
  150.     reverse(a, a + n);
  151.     calc_max_to(n);
  152.     for (int i = 0; i < n; i++)
  153.         max_r[i] = n - 1 - max_l[n - i - 1];
  154.     reverse(a, a + n);
  155.     calc_max_to(n);
  156.  
  157.     /*for (int i = 0; i < n; i++)
  158.         cout << max_l[i] << " ";
  159.     cout << "\n";
  160.     for (int i = 0; i < n; i++)
  161.         cout << max_r[i] << " ";
  162.     cout << "\n";*/
  163.  
  164.     vector<pair<int, int> > st;
  165.     st.push_back({inf, -1});
  166.     for (int i = 0; i < n; i++)
  167.     {
  168.         while (a[i] >= st.back().fi)
  169.             st.pop_back();
  170.         to_l[i] = st.back().se + 1;
  171.         st.push_back({a[i], i});
  172.     }
  173.     st.clear();
  174.     st.push_back({inf, n});
  175.     for (int i = n - 1; i >= 0; i--)
  176.     {
  177.         while (a[i] > st.back().fi)
  178.             st.pop_back();
  179.         to_r[i] = st.back().se - 1;
  180.         st.push_back({a[i], i});
  181.     }
  182.  
  183.     /*cout << "\n";
  184.     for (int i = 0; i < n; i++)
  185.         cout << to_l[i] << " ";
  186.     cout << "\n";
  187.     for (int i = 0; i < n; i++)
  188.         cout << to_r[i] << " ";
  189.     cout << "\n";
  190.     cout << "\n";*/
  191.  
  192.     int sum = 0;
  193.     for (int i = 0; i < n; i++)
  194.         sum += min(i - to_l[i] + 1, to_r[i] - i + 1);
  195.     assert(sum <= 3000000);
  196.  
  197.     build(n);
  198.     for (int i = 0; i < n; i++)
  199.         if (to_r[i] - i <= i - to_l[i])
  200.         {
  201.             for (int j = i; j <= to_r[i]; j++)
  202.             {
  203.                 int l = max(to_l[i], j - a[i] + 1), r = min(max_l[j], i);
  204.                 if (l <= r)
  205.                 {
  206.                     int cnt = 0;
  207.                     if (l == 0)
  208.                     {
  209.                         cnt++;
  210.                         l++;
  211.                     }
  212.                     cnt += get(0, 0, cnt_v, l - 1, r);
  213.                     if (cnt >= MOD)
  214.                         cnt -= MOD;
  215.                     upd(0, 0, cnt_v, j, j + 1, cnt);
  216.                 }
  217.             }
  218.         }
  219.         else
  220.         {
  221.             for (int j = i; j >= to_l[i]; j--)
  222.             {
  223.                 int l = max(i, max_r[j]), r = min(to_r[i], j + a[i] - 1);
  224.                 if (l <= r)
  225.                 {
  226.                     int cnt = (j == 0 ? 1 : get(0, 0, cnt_v, j - 1, j));
  227.                     upd(0, 0, cnt_v, l, r + 1, cnt);
  228.                 }
  229.             }
  230.         }
  231.     /*for (int i = 0; i < n; i++)
  232.         cout << get(0, 0, cnt_v, i, i + 1) << " ";
  233.     cout << "\n";*/
  234.     cout << get(0, 0, cnt_v, n - 1, n) << "\n";
  235.     return 0;
  236. }
Success #stdin #stdout 0s 33600KB
comments (?)
stdin
copy 
7
1 6 2 3 4 3 4
stdout
copy 
6
https://ideone.com/rz3ucF
language:
C++14 (gcc 8.3)
created:
4 years 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!