oj.uz

Submission #954434

# Submission time Handle Problem Language Result Execution time Memory
954434 2024-03-27T21:42:04 Z asdasdqwer Secret (JOI14_secret) C++14
100 / 100
 386 ms 4852 KB 
#include "secret.h"

const int MX = 1000;
int dat[10][MX];
int mask[MX];
int a[MX];


void divi(int l, int r, int lev) {
    if (l == r) return;
    int m = (l+r)/2;
    dat[lev][m] = a[m];
    for (int i=m-1;i>=l;i--) {
        dat[lev][i] = Secret(a[i], dat[lev][i+1]);
    }

    dat[lev][m+1] = a[m+1];
    for (int i=m+2;i<=r;i++) {
        dat[lev][i] = Secret(dat[lev][i-1], a[i]);
    }

    for (int i=m+1;i<=r;i++) {
        mask[i] ^= (1<<lev);
    }

    divi(l, m, lev+1);
    divi(m+1, r, lev+1);
}

void Init(int N, int A[]) {
    for (int i=0;i<N;i++) {
        a[i] = A[i];
    }

    divi(0, N-1, 0);
}

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 3668 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 110 ms 3924 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 104 ms 3668 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 366 ms 4436 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 362 ms 4852 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 356 ms 4464 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 362 ms 4268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 364 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 371 ms 4512 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 386 ms 4448 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1