oj.uz

Submission #738598

# Submission time Handle Problem Language Result Execution time Memory
738598 2023-05-09T07:05:56 Z MEGalodon Secret (JOI14_secret) C++14
100 / 100
 431 ms 4420 KB 
#include "secret.h"
#define MAXN 1001

int dat[MAXN][12];
int mask[MAXN];
void divi(int l, int r, int lev, int A[]){ //zero indexed
    if( l == r ){ dat[l][11] = A[l]; return; }
    int m = (l+r)/2;
    dat[m][lev] = A[m];
    dat[m+1][lev] = A[m+1]; //makes a difference in this case
    for( int i{m-1} ; i >= l ; --i ) dat[i][lev] = Secret(A[i], dat[i+1][lev]);
    for( int i{m+2} ; i <= r ; ++i ) dat[i][lev] = Secret(dat[i-1][lev], A[i]);
    for( int i{m+1} ; i <= r ; ++i ) mask[i] ^= (1<<lev);
    divi(l, m, lev+1, A);
    divi(m+1, r, lev+1, A);
}
void Init(int N, int A[]) {
    divi(0, N-1, 0, A);
    return;
}

int Query(int L, int R) {
    if( L == R ) return dat[L][11];
    int bts = __builtin_ctz(mask[L]^mask[R]);
    int ans = Secret(dat[L][bts], dat[R][bts]);
    return ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2516 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 122 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 120 ms 2388 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 426 ms 4392 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 421 ms 4420 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 421 ms 4396 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 426 ms 4336 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 429 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 421 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 431 ms 4300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1