Submission #978702

#TimeUsernameProblemLanguageResultExecution timeMemory
978702chautanphatSecret (JOI14_secret)C++14
100 / 100
361 ms4568 KiB
#include "secret.h" const int maxn = 1e3; int mask[maxn], a[maxn]; long long ans[10][maxn]; void dnc(int l, int r, int level = 0) { if (l == r) return; int mid = (l + r) / 2; ans[level][mid] = a[mid]; for (int i = mid - 1; i >= l; i--) ans[level][i] = Secret(a[i], ans[level][i + 1]); ans[level][mid + 1] = a[mid + 1]; for (int i = mid + 2; i <= r; i++) ans[level][i] = Secret(ans[level][i - 1], a[i]); dnc(l, mid, level + 1); dnc(mid + 1, r, level + 1); for (int i = mid + 1; i <= r; i++) mask[i] |= 1 << level; } void Init(int N, int A[]) { for (int i = 0; i < N; i++) a[i] = A[i]; dnc(0, N - 1); } int Query(int L, int R) { if (L == R) return a[L]; int level = __builtin_ctz(mask[L] ^ mask[R]); return Secret(ans[level][L], ans[level][R]); }
#Verdict Execution timeMemoryGrader output
Fetching results...