oj.uz

Submission #476792

# Submission time Handle Problem Language Result Execution time Memory
476792 2021-09-28T14:04:25 Z Karliver Secret (JOI14_secret) C++14
100 / 100
 539 ms 4328 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2500 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 2336 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 2372 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 515 ms 4296 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 506 ms 4196 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 504 ms 4276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 509 ms 4328 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 524 ms 4240 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 539 ms 4248 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 531 ms 4296 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1