Submission #926635

#TimeUsernameProblemLanguageResultExecution timeMemory
926635myst6Secret (JOI14_secret)C++17
100 / 100
366 ms4612 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include "secret.h" const int maxn = 1000; int table[10][maxn]; int mask[maxn]; int base[maxn]; int B = 0; void fill(int L, int R) { if (L == R) return; int M = (L + R) / 2; table[B][M] = base[M]; table[B][M+1] = base[M+1]; for (int i=M-1; i>=L; i--) table[B][i] = Secret(base[i], table[B][i+1]); for (int i=M+2; i<=R; i++) table[B][i] = Secret(table[B][i-1], base[i]); for (int i=M+1; i<=R; i++) mask[i] ^= 1 << B; ++B; fill(L, M); fill(M+1, R); --B; } void Init(int N, int A[]) { for (int i=0; i<N; i++) base[i] = A[i]; fill(0, N-1); } int Query(int L, int R) { if (L == R) return base[L]; int B = __builtin_ctz(mask[L] ^ mask[R]); return Secret(table[B][L], table[B][R]); }
#Verdict Execution timeMemoryGrader output
Fetching results...