oj.uz

Submission #464680

# Submission time Handle Problem Language Result Execution time Memory
464680 2021-08-13T16:41:05 Z bonopo Dojave (COCI17_dojave) C++14
112 / 140
 670 ms 192196 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 2 ms 1356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2636 KB Output is correct
2 Correct 4 ms 2508 KB Output is correct
3 Correct 4 ms 2508 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10336 KB Output is correct
2 Correct 22 ms 11340 KB Output is correct
3 Correct 30 ms 20676 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10328 KB Output is correct
2 Correct 44 ms 23252 KB Output is correct
3 Correct 71 ms 43124 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 44224 KB Output is correct
2 Correct 103 ms 48312 KB Output is correct
3 Correct 62 ms 43080 KB Output is correct

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 670 ms 192192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 651 ms 192196 KB Output isn't correct
2 Halted 0 ms 0 KB -