oj.uz

Submission #473260

# Submission time Handle Problem Language Result Execution time Memory
473260 2021-09-15T11:02:20 Z ljuba Secret (JOI14_secret) C++17
100 / 100
 562 ms 4492 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 1005;
int mask[mxN];
int value[20][mxN];
int A[mxN];

//maybe too much queries?


void solve(int l, int r, int dep = 0) {
    if(l == r) {
        value[dep][l] = A[l];
        return;
    }

    int m = (l + r) / 2;
    value[dep][m] = A[m];

    for(int i = m-1; i >= l; --i) {
        value[dep][i] = Secret(A[i], value[dep][i+1]);
    }

    value[dep][m+1] = A[m+1];

    for(int i = m+2; i <= r; ++i) {
        value[dep][i] = Secret(value[dep][i-1], A[i]);
    }

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

    solve(l, m, dep+1);
    solve(m+1, r, dep+1);
}

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

    solve(0, N-1);
}

int Query(int L, int R) {
    if(L == R) {
        return A[L];
    }

    int bits = __builtin_ctz(mask[L]^mask[R]);
    int levo = value[bits][L];
    int desno = value[bits][R];
    return Secret(levo, desno);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 2432 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 181 ms 2472 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 152 ms 2500 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 548 ms 4400 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 562 ms 4408 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 530 ms 4492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 532 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 546 ms 4428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 557 ms 4400 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 527 ms 4324 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1