Submission #720096

#TimeUsernameProblemLanguageResultExecution timeMemory
720096ifateenSecret (JOI14_secret)C++14
0 / 100
423 ms4468 KiB
#include <bits/stdc++.h> #include "secret.h" using namespace std; struct SparseTable { int N, LOG; vector<vector<int>> table; void init(vector<int> &v) { N = v.size(); LOG = __builtin_clz(1) - __builtin_clz(N); table.resize(LOG + 1); table[0] = v; for (int i = 1; i <= LOG; i++) { table[i].resize(N - (1 << i) + 1); for (int j = 0; j + (1 << i) <= N; j++) { table[i][j] = Secret(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); } } } int query(int L, int R) { int LOG2 = __builtin_clz(1) - __builtin_clz(R - L + 1); return Secret(table[LOG2][L], table[LOG2][R - (1 << LOG2) + 1]); } }; SparseTable s; void Init(int N, int A[]) { vector<int> v(N); int cnt = 0; for (auto &i : v) i = A[cnt++]; s.init(v); } int Query(int L, int R) { return s.query(L, R); } int Secret(int X, int Y);
#Verdict Execution timeMemoryGrader output
Fetching results...