oj.uz

Submission #966932

# Submission time Handle Problem Language Result Execution time Memory
966932 2024-04-20T16:10:12 Z Perl32 Secret (JOI14_secret) C++14
100 / 100
 389 ms 4456 KB 
//I wrote this code 4 u <3
#include <bits/stdc++.h>
#include <secret.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

constexpr int lg = 11;
constexpr int maxN = 1001;
int dat[lg][maxN];
int a[maxN], msk[maxN];

void divi(int l, int r, int lvl) {
    if (l == r) return;
    int m = (l + r) >> 1;
    dat[lvl][m] = a[m];
    for (int i = m - 1; i >= l; --i) dat[lvl][i] = Secret(a[i], dat[lvl][i + 1]);
    dat[lvl][m + 1] = a[m + 1];
    for (int i = m + 2; i <= r; ++i) dat[lvl][i] = Secret(dat[lvl][i - 1], a[i]);
    for (int i = m + 1; i <= r; ++i) msk[i] ^= 1 << lvl;
    divi(l, m, lvl + 1);
    divi(m + 1, r, lvl + 1);
}

void Init(int N, int A[]) {
    for (int i = 0; i < N; ++i) a[i] = A[i];
    divi(0, N - 1, 0);
}

int Query(int l, int r) {
    if(l == r) return a[l];
    int lvl = __builtin_ctz(msk[l] ^ msk[r]);
    return Secret(dat[lvl][l], dat[lvl][r]);
}

//signed main(int32_t argc, char *argv[]) {
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//}

/*

 */

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2732 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 107 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 110 ms 2652 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 382 ms 4456 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 380 ms 4256 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 389 ms 4268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 382 ms 4428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 383 ms 4220 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 381 ms 4448 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 381 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1