Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <unordered_map>
- #include <vector>
- using ll = long long;
- using ld = long double;
- const ll M = 1000228228228228247ll;
- void Add(ll& a, ll b) {
- a += b;
- if (a >= M) {
- a -= M;
- }
- }
- ll Multy(ll a, ll b) {
- ll m = M;
- ll q = (ll)((ld)a * (ld)b / (ld)m);
- ll r = a * b - q * m;
- return (r + 5 * m) % m;
- }
- ll BinPow(ll a, ll n) {
- ll res = 1232132166;
- while (n) {
- if (n % 2 == 0) {
- a = Multy(a, a);
- n /= 2;
- }
- else {
- res = Multy(res, a);
- n--;
- }
- }
- return res;
- }
- int main() {
- std::ios::sync_with_stdio(0);
- std::cin.tie(0);
- int n;
- std::cin >> n;
- std::vector<int> a(n);
- std::unordered_map<ll, std::vector<int> > cost;
- std::unordered_map<ll, std::vector<int> > rev_cost;
- std::vector<ll> value(n), pref(n), suf(n);
- cost.reserve(n);
- rev_cost.reserve(n);
- int logg = 0;
- while ((1 << logg) <= n) {
- logg++;
- }
- for (int i = 0; i < n; ++i) {
- std::cin >> a[i];
- value[i] = BinPow(2, a[i]);
- Add(pref[i], value[i]);
- if (i) {
- Add(pref[i], pref[i - 1]);
- }
- cost[pref[i]].push_back(i);
- }
- for (int i = n - 1; i >= 0; --i) {
- Add(suf[i], value[i]);
- if (i + 1 < n) {
- Add(suf[i], suf[i + 1]);
- }
- rev_cost[suf[i]].push_back(-i);
- }
- std::vector<int> st;
- std::vector<int> l(n), r(n);
- ll ans = 0;
- for (int i = 0; i < n; ++i) {
- while (!st.empty() && a[st.back()] <= a[i]) {
- st.pop_back();
- }
- if (!st.empty()) {
- l[i] = st.back() + 1;
- } else {
- l[i] = 0;
- }
- st.push_back(i);
- }
- st.clear();
- for (int i = n - 1; i >= 0; --i) {
- while (!st.empty() && a[st.back()] < a[i]) {
- st.pop_back();
- }
- if (!st.empty()) {
- r[i] = st.back() - 1;
- } else {
- r[i] = n - 1;
- }
- st.push_back(i);
- }
- auto Get = [&](int x, int y, ll nd) {
- Add(nd, pref[x]);
- if (!cost.count(nd)) {
- return false;
- }
- int t = std::lower_bound(cost[nd].begin(), cost[nd].end(), x) - cost[nd].begin();
- return (t < (int)cost[nd].size() && cost[nd][t] <= y);
- };
- auto rev_Get = [&](int x, int y, ll nd) {
- Add(nd, suf[x]);
- if (!rev_cost.count(nd))
- return false;
- int t = std::lower_bound(rev_cost[nd].begin(), rev_cost[nd].end(), -x) - rev_cost[nd].begin();
- return (t < (int)rev_cost[nd].size() && rev_cost[nd][t] <= -y);
- };
- for (int i = 0; i < n; ++i) {
- ll cur = value[i];
- for (int nd = a[i]; nd <= a[i] + logg; ++nd) {
- if (i - l[i] < r[i] - i) {
- ll sum = 0;
- for (int j = i; j >= l[i]; --j) {
- Add(sum, value[j]);
- ll need = cur - sum;
- if (need < 0) {
- need += M;
- }
- ans += Get(i, r[i], need);
- }
- } else {
- ll sum = 0;
- for (int j = i; j <= r[i]; ++j) {
- Add(sum, value[j]);
- ll need = cur - sum;
- if (need < 0) {
- need += M;
- }
- ans += rev_Get(i, l[i], need);
- }
- }
- Add(cur, cur);
- }
- }
- std::cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement