oj.uz

Submission #731644

# Submission time Handle Problem Language Result Execution time Memory
731644 2023-04-27T17:36:02 Z PanosPask Secret (JOI14_secret) C++14
100 / 100
 462 ms 4532 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

vector<vector<int>> saved;

// The i-th bit of mask[a] is 1 if a is to the right of the respective mid in that level
int n;
vector<int> mask;
vector<int> vals;

void divide(int lx, int rx, int level)
{
    if (lx == rx - 1)
        return;

    int mid = (lx + rx) / 2;

    saved[level][mid - 1] = vals[mid - 1];
    for (int i = mid - 2; i >= lx; i--)
        saved[level][i] = Secret(vals[i], saved[level][i + 1]);

    saved[level][mid] = vals[mid];
    for (int i = mid + 1; i < rx; i++)
        saved[level][i] = Secret(saved[level][i - 1], vals[i]);
    for (int i = mid; i < rx; i++) {
        // Set the i-th bit to 1 to indicate we are at the right
        mask[i] = mask[i] | (1<<level);
    }

    divide(lx, mid, level + 1);
    divide(mid, rx, level + 1);
}

void Init(int N, int A[])
{
    vals.resize(N);
    for (int i = 0; i < N; i++)
        vals[i] = A[i];

    n = N;
    int levels = ceil(log2(n));

    saved.resize(levels, vector<int>(n));
    mask.resize(n);

    divide(0, n, 0);
}

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

    // Find the first position in which the masks differ => the level we should look at
    int level = __builtin_ctz(mask[L] ^ mask[R]);

    int res = Secret(saved[level][L], saved[level][R]);
    return res;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2380 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 125 ms 2456 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 126 ms 2420 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 447 ms 4300 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 451 ms 4452 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 438 ms 4348 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 452 ms 4376 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 434 ms 4400 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 457 ms 4532 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 462 ms 4352 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1