oj.uz

Submission #447250

# Submission time Handle Problem Language Result Execution time Memory
447250 2021-07-25T13:43:46 Z zaneyu Secret (JOI14_secret) C++14
100 / 100
 526 ms 4440 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 144 ms 2448 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 147 ms 2464 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 2468 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 4440 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 526 ms 4292 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 521 ms 4316 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 519 ms 4356 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 523 ms 4268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 515 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 514 ms 4420 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1