Submission #476792

#	Time	Username	Problem	Language	Result	Execution time	Memory
476792		Karliver	Secret (JOI14_secret)	C++14	100 / 100	539 ms	4328 KiB

secret

#include "secret.h"
const int maxn=1e3+5;
int dat[12][maxn],msk[maxn];
int arr[maxn];
void rec(int l,int r,int lev){
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    dat[lev][mid]=arr[mid];
    for(int i=mid-1;i>=l;i--) dat[lev][i]=Secret(arr[i],dat[lev][i+1]);
    dat[lev][mid+1]=arr[mid+1];
    for(int i=mid+2;i<=r;i++) dat[lev][i]=Secret(dat[lev][i-1],arr[i]);
    for(int i=mid+1;i<=r;i++) msk[i]^=(1<<lev);
    rec(l,mid,lev+1);
    rec(mid+1,r,lev+1);
}
void Init(int N, int A[]) {
    for(int i=0;i<N;i++) arr[i]=A[i];
    rec(0,N-1,0);
}   
 
int Query(int l,int r) {
    if(l==r){
        return arr[l];
    }
    int bits=__builtin_ctz(msk[l]^msk[r]);
    return Secret(dat[bits][l],dat[bits][r]);
}

• Subtask 1: 100 / 100