oj.uz

Submission #788031

# Submission time Handle Problem Language Result Execution time Memory
788031 2023-07-19T16:41:40 Z kamelfanger83 Secret (JOI14_secret) C++17
100 / 100
 384 ms 4520 KB 
#include "secret.h"
#include <vector>

using namespace std;

const int maxD = 10;

vector<int> toright [maxD], toleft [maxD];
int *CA;

void Init(int N, int A[]) {
    CA = A;
    for (int rz = 0; rz < maxD; ++rz) {
        toright[rz].resize(N);
        toleft[rz].resize(N);
    }
    for (int k = 0; k < maxD; k++){
        for (int cen = 1 << k; cen < N; cen += 1 << (k+1)) {
            toright[k][cen - 1] = A[cen - 1];
            for (int lpop = cen - 2; lpop >= cen - (1 << k); --lpop) {
                toright[k][lpop] = Secret(A[lpop], toright[k][lpop + 1]);
            }
            toleft[k][cen] = A[cen];
            for (int rpop = cen + 1; rpop < min(N, cen + (1 << k)); ++rpop) {
                toleft[k][rpop] = Secret(toleft[k][rpop - 1], A[rpop]);
            }
        }
    }
}

int log2C(int n){
    int res = 0;
    while (n >> 1){
        n >>= 1;
        res++;
    }
    return res;
}

int Query(int L, int R) {
    if (L == R) return CA[L];
    int st = log2C(L ^ R);
    return Secret(toright[st][L], toleft[st][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 2364 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 108 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 108 ms 2284 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 378 ms 4340 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 377 ms 4236 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
6 Correct 381 ms 4248 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
7 Correct 380 ms 4344 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
8 Correct 384 ms 4312 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
9 Correct 376 ms 4240 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
10 Correct 377 ms 4520 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1