Submission #464680

#TimeUsernameProblemLanguageResultExecution timeMemory
464680bonopoDojave (COCI17_dojave)C++14
112 / 140
670 ms192196 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define rc (i<<1)|1 #define lc (i<<1) #define el "\n" #define f first #define s second typedef long long ll; const int MM=(1<<20)+5, MOD=1e9+7, LOG=20; ll N, M, a[MM], p[MM], dp[MM], sp[LOG][MM]; set<int> st; int lg2(int x) { return 32-__builtin_clz(x)-1; } int qry(int l, int r) { int lg=lg2(r-l+1); return min(sp[lg][l], sp[lg][r-(1<<lg)+1]); } int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); cin>>M; N=(1<<M); st.insert(0); if(M==1) { return cout<<2<<el, 0; } for(int i=1; i<=N; ++i) { cin>>a[i], p[a[i]]=i; } for(int i=1; i<=N; ++i) { sp[0][i]=p[a[i]^(N-1)]; } for(int i=1; i<LOG; ++i) { for(int j=1; j+(1<<i)-1<=N; ++j) sp[i][j]=min(sp[i-1][j], sp[i-1][j+(1<<(i-1))]); } for(int i=1; i<=N; ++i) { if(sp[0][i]>i) { st.insert(i); continue; } else st.erase(sp[0][i]); int lmt=*st.rbegin(); int rit=min(i-3, (int)sp[0][i]); while(rit>lmt) { int q=qry(rit, i); if(q==rit&&((i-rit+1)%4)==0) { dp[i]=1LL+dp[rit-1]; break; } else rit=min(q, rit-1); } } ll ans=((ll)N)*(N+1)/2LL; for(int i=1; i<=N; ++i) ans-=dp[i]; cout<<ans<<el; } // MM
#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...