Submission #971740

#TimeUsernameProblemLanguageResultExecution timeMemory
971740Art_ogoSecret (JOI14_secret)C++17
0 / 100
403 ms4436 KiB
#include <bits/stdc++.h> #include "secret.h" using namespace std; typedef pair<int, int> pii; const int MAXN = 1e3+10, LG = 10; int msk[MAXN]; int t[LG][MAXN]; int a[MAXN]; int n; void build(int l, int r, int v){ if(l == r){ t[v][l] = a[l]; return; } int m = (l + r) >> 1; t[v][m] = a[m]; msk[m] ^= 1 << v; for(int i = m - 1; i >= l; i--){ t[v][i] = Secret(a[i], t[v][i + 1]); msk[i] ^= 1 << v; } t[v][m + 1] = a[m + 1]; for(int i = m + 2; i <= r; i++) t[v][i] = Secret(t[v][i - 1], a[i]); build(l, m, v + 1); build(m + 1, r, v + 1); } void Init(int N, int A[]){ n = N; for(int i = 0; i < N; i++) a[i] = A[i]; build(0, N - 1, 0); } int Query(int L, int R){ if(L == R) return a[L]; int cur = __builtin_ctz(msk[L]^msk[R]); return Secret(t[cur][L], t[cur][R]); }
#Verdict Execution timeMemoryGrader output
Fetching results...