Submission #1126114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126114		anmattroi	Secret (JOI14_secret)	C++20	100 / 100	417 ms	4452 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

int n;
int a[1024];
int f[10][1024];

void Init(int N, int A[]) {
    n = N; int oldn = N;
    for (int i = 0; i < n; i++) a[i] = A[i];
    while (__builtin_popcount(n) > 1) a[n++] = 0;

    int sz = __lg(n);
    for (int level = 0; level < sz; level++) {
        for (int block = 0; block < (1<<level); block++) {
            int start = (block<<(sz-level)),
                fin = ((block + 1) << (sz-level)),
                middle = (start+fin)>>1;
            if (start >= oldn) break;
            f[level][middle] = a[middle];
            for (int x = middle+1; x < min(fin, oldn); x++) f[level][x] = Secret(f[level][x-1], a[x]);

            middle = min(middle, oldn);
            f[level][middle-1] = a[middle-1];
            for (int x = middle - 2; x >= start;x--) f[level][x] = Secret(a[x], f[level][x+1]);
        }
    }
}

int Query(int L, int R) {
    if (L == R) return a[L];
    int level = __lg(n)-__lg(L^R)-1;
    return Secret(f[level][L], f[level][R]);
    return 0;
}

• Subtask 1: 100 / 100