| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1325787 | sonarcht | Secret (JOI14_secret) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "secret.h"
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(v) begin(v), end(v)
#define pll pair<ll, ll>
#define fi first
#define se second
#define vll vector<ll>
#define mll map<ll, ll>
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll N = 1e5 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans, a[N], dat[N][21], mask[N];
void dnc(ll l, ll r, ll dep, ll a[]) {
if (l == r) {
dat[l][dep] = a[l];
return;
}
ll m = (l+r) / 2;
dat[m][dep] = a[m], dat[m+1][dep] = a[m+1];
for (int i = m-1; i >= l; --i) dat[i][dep] = Secret(a[i], dat[i+1][dep]);
for (int i = m+2; i <= r; ++i) dat[i][dep] = Secret(dat[i-1][dep], a[i]);
for (int i = m+1; i <= r; ++i) mask[i] ^= (1 << dep);
dnc(l, mid, dep+1, a);
dnc(mid+1, r, dep+1, a);
}
void Init(ll N, ll A[]) {
n = N;
dnc(0, n-1, 0, A);
}
ll Query(ll L, ll R) {
ll dep = __builtin_ctz(mask[l] ^ mask[r]);
return Secret(dat[l][dep], dat[r][dep]);
}