oj.uz

Submission #391542

# Submission time Handle Problem Language Result Execution time Memory
391542 2021-04-19T09:29:35 Z KoD Secret (JOI14_secret) C++17
100 / 100
 510 ms 4576 KB 
#include "secret.h"

int MSB(int x) {
    return 31 - __builtin_clz(x);
}

int table[10][1000];

void Init(int N, int A[]) {
    for (int i = 0; i < N; ++i) {
        table[0][i] = A[i];
    }
    for (int k = 1; k < 10; ++k) {
        const int len = (1 << k);
        for (int mid = len; mid < N; mid += 2 * len) {
            table[k][mid - 1] = A[mid - 1];
            table[k][mid] = A[mid];
            for (int i = 1; i < len; ++i) {
                table[k][mid - i - 1] = Secret(A[mid - i - 1], table[k][mid - i]);
                if (mid + i < N) {
                    table[k][mid + i] = Secret(table[k][mid + i - 1], A[mid + i]);
                }
            }
        }
    }
}

int Query(int L, int R) {
    if (L == R) {
        return table[0][L];
    }
    const auto k = MSB(L ^ R);
    return Secret(table[k][L], table[k][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2372 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 142 ms 2396 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 2500 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 502 ms 4292 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 508 ms 4292 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
6 Correct 510 ms 4264 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
7 Correct 504 ms 4336 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
8 Correct 507 ms 4576 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
9 Correct 499 ms 4292 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
10 Correct 505 ms 4316 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1