ilyasizov

Untitled

Jun 25th, 2021
1,061
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <unordered_map>
  4. #include <vector>
  5.  
  6. using ll = long long;
  7. using ld = long double;
  8.  
  9. const ll M = 1000228228228228247ll;
  10.  
  11. void Add(ll& a, ll b) {
  12.     a += b;
  13.     if (a >= M) {
  14.         a -= M;
  15.     }
  16. }
  17.  
  18. ll Multy(ll a, ll b) {
  19.     ll m = M;
  20.     ll q = (ll)((ld)a * (ld)b / (ld)m);
  21.     ll r = a * b - q * m;
  22.     return (r + 5 * m) % m;
  23. }
  24.  
  25. ll BinPow(ll a, ll n) {
  26.     ll res = 1232132166;
  27.     while (n) {
  28.         if (n % 2 == 0) {
  29.             a = Multy(a, a);
  30.             n /= 2;
  31.         }
  32.         else {
  33.             res = Multy(res, a);
  34.             n--;
  35.         }
  36.     }
  37.     return res;
  38. }
  39.  
  40. int main() {
  41.     std::ios::sync_with_stdio(0);
  42.     std::cin.tie(0);
  43.     int n;
  44.     std::cin >> n;
  45.  
  46.     std::vector<int> a(n);
  47.     std::unordered_map<ll, std::vector<int> > cost;
  48.     std::unordered_map<ll, std::vector<int> > rev_cost;
  49.     std::vector<ll> value(n), pref(n), suf(n);
  50.     cost.reserve(n);
  51.     rev_cost.reserve(n);
  52.  
  53.     int logg = 0;
  54.     while ((1 << logg) <= n) {
  55.         logg++;
  56.     }
  57.  
  58.     for (int i = 0; i < n; ++i) {
  59.         std::cin >> a[i];
  60.         value[i] = BinPow(2, a[i]);
  61.         Add(pref[i], value[i]);
  62.         if (i) {
  63.             Add(pref[i], pref[i - 1]);
  64.         }
  65.         cost[pref[i]].push_back(i);
  66.     }
  67.  
  68.     for (int i = n - 1; i >= 0; --i) {
  69.         Add(suf[i], value[i]);
  70.         if (i + 1 < n) {
  71.             Add(suf[i], suf[i + 1]);
  72.         }
  73.         rev_cost[suf[i]].push_back(-i);
  74.     }
  75.  
  76.     std::vector<int> st;
  77.     std::vector<int> l(n), r(n);
  78.     ll ans = 0;
  79.  
  80.     for (int i = 0; i < n; ++i) {
  81.         while (!st.empty() && a[st.back()] <= a[i]) {
  82.             st.pop_back();
  83.         }
  84.         if (!st.empty()) {
  85.             l[i] = st.back() + 1;
  86.         } else {
  87.             l[i] = 0;
  88.         }
  89.         st.push_back(i);
  90.     }
  91.  
  92.     st.clear();
  93.  
  94.     for (int i = n - 1; i >= 0; --i) {
  95.         while (!st.empty() && a[st.back()] < a[i]) {
  96.             st.pop_back();
  97.         }
  98.         if (!st.empty()) {
  99.             r[i] = st.back() - 1;
  100.         } else {
  101.             r[i] = n - 1;
  102.         }
  103.         st.push_back(i);
  104.     }
  105.  
  106.     auto Get = [&](int x, int y, ll nd) {
  107.         Add(nd, pref[x]);
  108.         if (!cost.count(nd)) {
  109.             return false;
  110.         }
  111.         int t = std::lower_bound(cost[nd].begin(), cost[nd].end(), x) - cost[nd].begin();
  112.         return (t < (int)cost[nd].size() && cost[nd][t] <= y);
  113.     };
  114.  
  115.     auto rev_Get = [&](int x, int y, ll nd) {
  116.         Add(nd, suf[x]);
  117.         if (!rev_cost.count(nd))
  118.             return false;
  119.         int t = std::lower_bound(rev_cost[nd].begin(), rev_cost[nd].end(), -x) - rev_cost[nd].begin();
  120.         return (t < (int)rev_cost[nd].size() && rev_cost[nd][t] <= -y);
  121.     };
  122.  
  123.     for (int i = 0; i < n; ++i) {
  124.         ll cur = value[i];
  125.         for (int nd = a[i]; nd <= a[i] + logg; ++nd) {
  126.             if (i - l[i] < r[i] - i) {
  127.                 ll sum = 0;
  128.                 for (int j = i; j >= l[i]; --j) {
  129.                     Add(sum, value[j]);
  130.                     ll need = cur - sum;
  131.                     if (need < 0) {
  132.                         need += M;
  133.                     }
  134.                     ans += Get(i, r[i], need);
  135.                 }
  136.             } else {
  137.                 ll sum = 0;
  138.                 for (int j = i; j <= r[i]; ++j) {
  139.                     Add(sum, value[j]);
  140.                     ll need = cur - sum;
  141.                     if (need < 0) {
  142.                         need += M;
  143.                     }
  144.                     ans += rev_Get(i, l[i], need);
  145.                 }
  146.             }
  147.             Add(cur, cur);
  148.         }
  149.     }
  150.     std::cout << ans;
  151.     return 0;
  152. }
RAW Paste Data