| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 111478 | vex | Secret (JOI14_secret) | C++14 | 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 maxn 1005
using namespace std;
int rez[12][maxn];
int to[maxn];
int tpp[maxn];
int nn;
void Init(int n,int a[])
{
nn=n;
for(int i=1;i<=n;i*=2)
{
int pos=n-i;
rez[i][0]=a[i];
for(int j=1;pos+j<n;j++)
{
rez[i][j]=Secret(rez[i][j-1],a[pos+j]);
}
to[pos-1]=a[pos-1];
tpp[pos-1]=i;
for(int j=pos-2;j>max(pos-2*i,-1);j--)
{
to[j]=Secret(a[j],to[j+1]);
tpp[j]=i;
}
}
}
int Query(int l,int r)
{
if(__builtin_popcount(nn-l)==1)
{
int x=log2(r-l+1);
if((1<<x)!=r-l+1)x++;
return rez[x][r-x];
}
else
{
return Secret(to[l],rez[tpp[l]][r-(nn-(1<<tpp[l]))])
}
}