| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1256694 | nguyenhuythach | Secret (JOI14_secret) | C++20 | 0 ms | 0 KiB |
#include "secret.h"
#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=1069;
int n;
int a[nmax],pfx[15][nmax],suf[15][nmax];
void dnc(int l,int r,int lv)
{
if(l==r)
{
suf[lv][l]=a[l];
return;
}
int mid=(l+r)/2;
//precase
suf[lv][mid]=a[mid];
pfx[lv][mid+1]=a[mid+1];
//build
REP(i,mid-1,l) suf[lv][i]=Secret(a[i],suf[lv][i+1]);
FOR(i,mid+2,r) pfx[lv][i]=Secret(pfx[lv][i-1],a[i]);
//recursion
dnc(l,mid,lv+1);
dnc(mid+1,r,lv+1);
}
void Init(int N, int A[])
{
n=N;
FOR(i,1,n) a[i]=A[i-1];
dnc(1,n,1);
}
pii get(int id, int l, int r, int u, int v) {
int mid = (l + r) / 2;
if (u <= mid && mid <= v) {
return {id, mid};
}
if (u > mid) {
return get(id + 1, mid + 1, r, u, v);
}
return get(id + 1, l, mid, u, v);
}
int Query(int L,int R)
{
int l=L+1,r=R+1;
auto save=find(1,1,n,l,r);
if(l==r) return a[l];
else if(r==save.se) return suf[save.fi][l];
else if(l==save.se) return pfx[save.fi][r];
else return Secret(suf[save.fi][l],pfx[save.fi][r]);
}