oj.uz

Submission #1099729

# Submission time Handle Problem Language Result Execution time Memory
1099729 2024-10-12T05:03:48 Z dzhoz0 Secret (JOI14_secret) C++17
100 / 100
 348 ms 4528 KB 
/*
    ghmt the cutie :3
          UwU
*/

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

#define INF 1e9
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MAXN = 1000;
const int LG = 9;
int st[LG + 1][MAXN], mask[MAXN];
vi v;
void preprocess(int l, int r, int k, int a[]) {
    if(l == r) return;
    int mid = (l + r) / 2;
    st[k][mid] = a[mid];
    for(int i = mid - 1; i >= l; i--) st[k][i] = Secret(a[i], st[k][i + 1]);
    st[k][mid + 1] = a[mid + 1];
    for(int i = mid + 2; i <= r; i++) st[k][i] = Secret(st[k][i - 1], a[i]);

    for(int i = mid + 1; i <= r; i++) mask[i] ^= (1 << k);
   
    preprocess(l, mid, k + 1, a);
    preprocess(mid + 1, r, k + 1, a);
}

void Init(int n, int a[]) {
    preprocess(0, n - 1, 0, a);
    for(int i = 0; i < n; i++) v.push_back(a[i]);
}

int Query(int l, int r) {
    if(l == r) return v[l];
    int bits = __builtin_ctz(mask[l] ^ mask[r]);
    return Secret(st[bits][l], st[bits][r]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2384 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 83 ms 2384 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 83 ms 2640 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 338 ms 4528 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 299 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 348 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 296 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 318 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 304 ms 4492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 304 ms 4528 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1