Submission #464680

#	Time	Username	Problem	Language	Result	Execution time	Memory
464680		bonopo	Dojave (COCI17_dojave)	C++14	112 / 140	670 ms	192196 KiB

dojave

#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

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14