Submission #1018195

#TimeUsernameProblemLanguageResultExecution timeMemory
1018195TsotneSVSecret (JOI14_secret)C++14
100 / 100
332 ms4448 KiB
#include "secret.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1000; const int maxlvl = 15; int n; int DVC[maxlvl][maxn]; void create(int lvl, int l, int r, int A[]) { if (l == r) { DVC[lvl][l] = A[l]; return; } int m = (l + r) >> 1; // left side DVC[lvl][m] = A[m]; for (int i = m - 1; i >= l; i--) DVC[lvl][i] = Secret(A[i], DVC[lvl][i + 1]); // right side DVC[lvl][m + 1] = A[m + 1]; for (int i = m + 2; i <= r; i++) DVC[lvl][i] = Secret(DVC[lvl][i - 1], A[i]); create(lvl + 1, l, m, A); create(lvl + 1, m + 1, r, A); } int get(int lvl, int l, int r, int L, int R) { if (l == r) return DVC[lvl][L]; int m = (l + r) >> 1; if (R <= m) return get(lvl + 1, l, m, L, R); if (L >= m+1) return get(lvl + 1, m+1, r, L, R); return Secret(DVC[lvl][L], DVC[lvl][R]); } void Init(int N, int A[]) { n = N; create(0, 0, n - 1, A); } int Query(int L, int R) { return get(0, 0, n - 1, L, R); }
#Verdict Execution timeMemoryGrader output
Fetching results...