# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
971741 | Art_ogo | Secret (JOI14_secret) | C++17 | 0 ms | 0 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 <bits/stdc++.h>
#include "secret.h"
#define int long long
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]);
}