oj.uz

Submission #1025320

# Submission time Handle Problem Language Result Execution time Memory
1025320 2024-07-16T19:53:11 Z a5a7 Secret (JOI14_secret) C++14
100 / 100
 333 ms 4444 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> v; int c;
vector<int> arr;
vector<int> mask;

void create(int left, int right, int depth){
    if (depth > 8) return;
    if (left == right){
        v[depth][left] = arr[left];
        return;
    }
    int mid = (left+right)/2;
    v[depth][mid] = arr[mid];
    v[depth][mid+1] = arr[mid+1];
    for (int i = mid-1; i >= left; i--) v[depth][i] = Secret(arr[i], v[depth][i+1]);
    for (int i = mid+2; i <= right; i++) v[depth][i] = Secret(v[depth][i-1], arr[i]);
    for (int i = mid+1; i <= right; i++) mask[i] ^= (1<<(c-depth-1));
    create(left, mid, depth+1);
    create(mid+1, right, depth+1);
}

void Init(int n, int a[]) {
    c = 0;
    while ((1<<c) < n) c++;
    arr = vector<int>(n);
    for (int i = 0; i < n; i++) arr[i] = a[i];
    mask = vector<int>(n, 0);
    v = vector<vector<int>>(c+2, vector<int>(n, 0));
    create(0, n-1, 0);
}

int Query(int left, int right) {
    if (left == right) return arr[left];
    if (left == (right-1)) return Secret(arr[left], arr[right]);
    int t = c-(32-(__builtin_clz(mask[left]^mask[right])));
    return Secret(v[t][left], v[t][right]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2680 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 84 ms 2652 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 84 ms 2648 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 305 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 309 ms 4216 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 333 ms 4444 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 291 ms 4400 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 306 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 307 ms 4260 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 305 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1