Submission #646284

#TimeUsernameProblemLanguageResultExecution timeMemory
646284inksamuraiDojave (COCI17_dojave)C++17
14 / 140
1 ms468 KiB
#include <bits/stdc++.h> // cut here #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder namespace atcoder { template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} segtree(int n) : segtree(std::vector<S>(n, e())) {} segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template <bool (*f)(S)> int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder // cut here using namespace std; #define int ll #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define rng(i,c,n) for(int i=c;i<n;i++) #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3dSgv16 ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} // e int op(int l,int r){return l+r;} int e(){return 0;} int opa(int l,int r){return max(l,r);} int ea(){return 0;} signed main(){ _3dSgv16; int ln; cin>>ln; assert(ln<=10); const int n=1<<ln; vi a(n); rep(i,n){ cin>>a[i]; } vi ps; rep(i,n){ ps.pb((!sz(ps)?0:ps.back())^a[i]); } vi ids(n); rep(i,n){ ids[a[i]]=i; } vi rbe(n); rep(i,n){ rbe[i]=ids[(n-1)^a[i]]; } atcoder::segtree<int,opa,ea> segma(rbe); int ans=(n*(n+1))/2; const int w=4; for(int d=0;d<w;d++){ atcoder::segtree<int,op,e> seg(n); priority_queue<int> pq; for(int i=d,t=0;i<n;i+=w,t+=1){ int l=0,r=t-1; int c=-1; while(l<=r){ int m=(l+r)/2; if(segma.prod(m*w+d+1,i+1)<=i){ c=m,r=m-1; }else{ l=m+1; } } if(c!=-1){ ans-=seg.prod(c*w+d,i); } // cut on i-th position pq.push(i); seg.set(i,1); int mi=n; rng(j,i+1,min(n,i+w+1)){ mi=min(mi,rbe[j]); } // if(i+w==8) print(mi); while(sz(pq)){ int j=pq.top(); if(j>=mi){ seg.set(j,0); pq.pop(); }else{ break; } } } } int ma=-1; rep(i,n){ ma=max(ma,rbe[i]); if(i%4==3){ if(ma<=i){ // cout<<i<<" "; ans-=1; } } } print(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...