# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1085788 | f0rizen | Secret (JOI14_secret) | C++17 | 325 ms | 4472 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
const int lg = 10;
int *a;
vector<int> st[lg];
vector<int> mask;
void Init(int N, int A[]) {
a = A;
for (int i = 0; i < lg; ++i) {
st[i].resize(N);
}
mask.resize(N);
auto calc = [&](auto calc, int l, int r, int k) -> void {
if (l == r) {
return;
}
int mid = (l + r) / 2;
st[k][mid] = A[mid];
for (int i = mid - 1; i >= l; --i) {
st[k][i] = Secret(A[i], st[k][i + 1]);
}
st[k][mid + 1] = A[mid + 1];
for (int i = mid + 2; i <= r; ++i) {
st[k][i] = Secret(st[k][i - 1], A[i]);
}
for (int i = mid + 1; i <= r; ++i) {
mask[i] ^= (1 << k);
}
calc(calc, l, mid, k + 1);
calc(calc, mid + 1, r, k + 1);
};
calc(calc, 0, N - 1, 0);
}
int Query(int L, int R) {
if (L == R) {
return a[L];
}
int k = __builtin_ctz(mask[L] ^ mask[R]);
return Secret(st[k][L], st[k][R]);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |