Submission #74342839

---

Source Code Expand

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }

using u64 = unsigned long long;

#include <unordered_set>

#include <initializer_list>

namespace nachia{

bool IsPrime(unsigned long long x){
    if(x <= 1 || x % 2 == 0) return x == 2;
    using u64 = unsigned long long;
    using u128 = __uint128_t;
    u64 d = x-1;
    int s = 0;
    int q = 63;
    while(!(d&1)){ d >>= 1; s++; }
    while(!(d >> q)) q--;
    u64 r = x; for(int t=0; t<6; t++) r *= 2-r*x;
    u128 n2 = -(u128)x % x;
    auto red = [=](u128 t) -> u64 {
        u64 g = (t + (u128)((u64)t*-r)*x) >> 64;
        return (g >= x || g < (t >> 64)) ? g-x : g;
    };
    u64 one = red(n2);
    for(u64 b : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }){
        if(b%x==0) continue;
        u64 a = b = red(b%x*n2);
        for(int e=q-1; e>=0; e--){ a = red((u128)a*a); if((d>>e)&1) a = red((u128)a*b); }
        if(a == one) continue;
        for(int t=1; t<s&&a!=x-one; t++) a = red((u128)a*a);
        if(a != x-one) return false;
    }
    return true;
}

} // namespace nachia

#include <cassert>

namespace nachia{

template<
    class S,
    S op(S l, S r)
>
struct Segtree {
private:
    int N;
    std::vector<S> A;
    int xN;

    void mergev(int i){
        if(i < N) A[i] = op(A[i*2], A[i*2+1]);
    }

    template<class E>
    int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(r <= a) return a;
        if(b <= r){
            S nx = op(A[i], x);
            if(cmp(nx)){ x = nx; return a; }
        }
        if(b - a == 1) return b;
        int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1);
        if(q > (a+b)/2) return q;
        return minLeft2(r, cmp, a, (a+b)/2, i*2);
    }
    
    template<class E>
    int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(b <= l) return b;
        if(l <= a){
            S nx = op(x, A[i]);
            if(cmp(nx)){ x = nx; return b; }
        }
        if(b - a == 1) return a;
        int q = maxRight2(l, cmp, a, (a+b)/2, i*2);
        if(q < (a+b)/2) return q;
        return maxRight2(l, cmp, (a+b)/2, b, i*2+1);
    }

public:
    Segtree() : N(0) {}
    Segtree(int n, S e) : xN(n) {
        N = 1; while (N < n) N *= 2;
        A.assign(N * 2, e);
    }
    Segtree(const std::vector<S>& a, S e) : Segtree(a.size(), e){
        for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i];
        for(int i=N-1; i>=1; i--) mergev(i);
    }

    S getE() const { return A[0]; }

    void set(int p, S x){
        assert(0 <= p); assert(p < xN);
        p += N; A[p] = x;
        for(int d=1; (1<<d)<=N; d++) mergev(p>>d);
    }

    S get(int p) const {
        assert(0 <= p); assert(p < xN);
        return A[N+p];
    }

    S prod(int l, int r) const {
        assert(0 <= l); assert(r <= xN);
        l += N; r += N;
        S ql = A[0], qr = A[0];
        while(l<r){
            if(l&1) ql = op(ql, A[l++]);
            if(r&1) qr = op(A[--r], qr);
            l /= 2;
            r /= 2;
        }
        return op(ql, qr);
    }

    S allProd() const { return A[1]; }

    // bool cmp(S)
    template<class E>
    int minLeft(int r, E cmp) const {
        return minLeft2(r, cmp);
    }

    // bool cmp(S)
    template<class E>
    int maxRight(int l, E cmp) const {
        int x = maxRight2(l, cmp);
        return x > xN ? xN : x;
    }
};

} // namespace nachia
#include <functional>
#include <utility>

namespace nachia {
    template<class T, class Cmp = std::less<T>>
    struct PointSetRangeMin{
    private:
        static T minop(T l, T r){ return std::min(l, r, Cmp()); }
        using Base = Segtree<T, minop>;
        Base base;
        Cmp cmpx;
    public:
        PointSetRangeMin() {}
        PointSetRangeMin(int len, T INF)
            : base(len, INF){}
        PointSetRangeMin(const std::vector<T>& init, T INF)
            : base(init, INF){}
        T min(int l, int r){ return base.prod(l, r); }
        T min(){ return base.allProd(); }
        void set(int pos, T val){ base.set(pos, val); }
        T getinf() const { return base.getE(); }
        void setinf(int pos){ set(pos, getinf()); }
        T get(int pos){ return base.get(pos); }
        void chmin(int pos, T val){ base.set(pos, minop(get(pos), val)); }
        int lBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return cmpx(val, x); }); }
        int uBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return !cmpx(x, val); }); }
        int lBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return cmpx(val, x); }); }
        int uBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return !cmpx(x, val); }); }
        template<class E>
        int minLeft(int r, E cmp){ return base.minLeft(r, cmp); }
        template<class E>
        int maxRight(int l, E cmp){ return base.maxRight(l, cmp); }
        int argmin(int l, int r){
            auto v = this->min(l, r);
            if(!cmpx(v, getinf())) return -1;
            return lBoundRight(l, v);
        }
    };
} // namespace nachia

#include <unordered_map>
#include <cstdint>
#include <array>


namespace nachia{

int Popcount(unsigned long long c){
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x){
    assert(x != 0ull);
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x){
    assert(x != 0ull);
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}


namespace nachia{

class Xoshiro256pp{
public:

    using i32 = int32_t;
    using u32 = uint32_t;
    using i64 = int64_t;
    using u64 = uint64_t;


private:
    std::array<u64, 4> s;

    // https://prng.di.unimi.it/xoshiro256plusplus.c
    static inline uint64_t rotl(const uint64_t x, int k) noexcept {
        return (x << k) | (x >> (64 - k));
    }
    inline uint64_t gen(void) noexcept {
        const uint64_t result = rotl(s[0] + s[3], 23) + s[0];
        const uint64_t t = s[1] << 17;
        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];
        s[2] ^= t;
        s[3] = rotl(s[3], 45);
        return result;
    }

    // https://xoshiro.di.unimi.it/splitmix64.c
    u64 splitmix64(u64& x) {
        u64 z = (x += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }

    // generate x : 0 <= x <= r
    u64 random_unsigned_from_zero(u64 r){
        if(!r) return 0;
        u64 mask = 1ull << MsbIndex(r);
        mask += mask - 1;
        while(true){
            auto res = rng64() & mask;
            if(res <= r) return res;
        }
    }

public:

    void seed(u64 x = 7001){
        assert(x != 0);
        s[0] = x;
        for(int i=1; i<4; i++) s[i] = splitmix64(x);
    }
    
    std::array<u64, 4> getState() const { return s; }
    void setState(std::array<u64, 4> a){ s = a; }

    Xoshiro256pp(){ seed(); }
    
    u64 rng64() { return gen(); }
    u64 operator()(){ return gen(); }

    // generate x : l <= x <= r
    u64 random_unsigned(u64 l,u64 r){
        assert(l<=r);
        return l + random_unsigned_from_zero(r - l);
    }

    // generate x : l <= x <= r
    i64 random_signed(i64 l,i64 r){
        assert(l<=r);
        return (i64)(random_unsigned_from_zero((u64)r - (u64)l) + (u64)l);
    }


    // permute x : n_left <= x <= n_right
    // output r from the front
    template<class Int>
    std::vector<Int> random_nPr(Int n_left, Int n_right, Int r){
        Int n = n_right-n_left;

        assert(n>=0);
        assert(r<=(1ll<<27));
        if(r==0) return {};  
        assert(n>=r-1);

        std::vector<Int> V;
        std::unordered_map<Int,Int> G;
        for(int i=0; i<r; i++){
            Int p = random_signed(i,n);
            Int x = p - G[p];
            V.push_back(x);
            G[p] = p - (i - G[i]);
        }

        for(Int& v : V) v+=n_left;
        return V;
    }

    // shuffle using swaps
    template<class E>
    void shuffle_inplace(std::vector<E>& V){
        size_t N = V.size();
        for(size_t i=1; i<N; i++){
            std::swap(V[i], V[random_unsigned(0, i)]);
        }
    }

    template<class E>
    std::vector<E> shuffled(const std::vector<E>& V){
        auto cp = V;
        shuffle_inplace(cp);
        return cp;
    }

};

} // namespace nachia
#include <random>
#include <chrono>
nachia::Xoshiro256pp rng;
namespace RngInitInstance { struct RngInit { RngInit(){
    unsigned long long seed1 = std::random_device()();
    unsigned long long seed2 = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    rng.seed(seed1 ^ seed2);
} } a; }

ll MOD = 0;
ll addMOD(ll l, ll r){
  ll v = l + r;
  return v >= MOD ? v - MOD : v;
}
ll subMOD(ll l, ll r){
  ll v = l - r;
  return v < 0 ? v + MOD : v;
}


void testcase(){
  ll N; cin >> N;
  V<ll> A(N); REP(i,N) cin >> A[i];
  while(!nachia::IsPrime(MOD)) MOD = rng.random_unsigned(1ll << 60, 1ll << 61);

  ll Z = *max_element(A.begin(), A.end()) + 30;

  nachia::PointSetRangeMin<ll, greater<ll>> ds(A, -1);

  V<ll> dig(Z);
  dig[0] = 1; REP(i,Z-1) dig[i+1] = addMOD(dig[i], dig[i]);

  V<ll> val(N+1, {0});
  REP(i,N) val[i+1] = addMOD(val[i], dig[A[i]]);

  ll ans = 0;

  auto dfs = [&](auto& dfs, ll l, ll r, unordered_set<ll> st) -> void {
    if(r - l == 1) return;
    ll m = ds.argmin(l, r-1) + 1;
    ll a = A[m-1];
    unordered_set<ll> lst, rst;
    if(m-l < r-m){
      swap(st, rst);
      for(ll i=l; i<m; i++){
        lst.insert(val[i]);
        rst.erase(val[i]);
      }
      for(auto v : lst) REP(f,18) ans += rst.count(addMOD(v, dig[a+f]));
    } else {
      swap(st, lst);
      for(ll i=m; i<r; i++){
        rst.insert(val[i]);
        lst.erase(val[i]);
      }
      for(auto v : rst) REP(f,18) ans += lst.count(subMOD(v, dig[a+f]));
    }
    dfs(dfs, l, m, move(lst)); dfs(dfs, m, r, move(rst));
  };

  dfs(dfs, 0, N+1, unordered_set<ll>(val.begin(), val.end()));

  cout << ans << "\n";
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  testcase();
  return 0;
}

Submission Info

Judge Result