# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1015726 | mnbvcxz123 | 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"
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define pb push_back
#define fi first
#define se second
constexpr int N=1e3+5;
constexpr int lg=11;
int res[lg][N];
int mask[N];
int a[N];
void build(int l, int r, int pw){
if(l==r)return;
int m=(l+r)>>1;
res[pw][m]=a[m];
for(int i=m-1;i>=l;--i)
res[pw][i]=Secret(a[i],res[pw][i+1]);
res[pw][m+1]=a[m+1];
for(int i=m+2;i<=r;++i)
res[pw][i]=Secret(res[pw][i-1],a[i]);
for(int i=m+1;i<=r;++r)
mask[i]^=1<<pw;
build(l,mid,pw+1);
build(mid+1,r,pw+1);
}
void Init(int n, int t[]){
for(int i=0;i<n;++i)
a[i]=t[i];
build(0,n-1,0);
}
int Query(int l, int r){
if(l==r)return a[l];
int x=__builtin_ctz(mask[l]^mask[r]);
return Secret(res[x][l],res[x][r]);
}