oj.uz

Submission #926621

# Submission time Handle Problem Language Result Execution time Memory
926621 2024-02-13T12:42:23 Z myst6 Secret (JOI14_secret) C++14
100 / 100
 395 ms 4568 KB 
#include <bits/stdc++.h>
#include "secret.h"

const int maxn = 1000;
int table[10][maxn];
int mask[maxn];
int base[maxn];

void fill(int L, int R, int B) {
  if (L == R) return;
  int M = (L + R) / 2;
  table[B][M] = base[M];
  table[B][M+1] = base[M+1];
  for (int i=M-1; i>=L; i--) table[B][i] = Secret(base[i], table[B][i+1]);
  for (int i=M+2; i<=R; i++) table[B][i] = Secret(table[B][i-1], base[i]);
  for (int i=M+1; i<=R; i++) mask[i] ^= 1 << B;
  fill(L, M, B+1);
  fill(M+1, R, B+1);
}

void Init(int N, int A[]) {
  std::memset(mask, 0, sizeof mask);
  for (int i=0; i<N; i++) base[i] = A[i];
  fill(0, N-1, 0);
}

int Query(int L, int R) {
  if (L == R) return base[L];
  int B = __builtin_ctz(mask[L] ^ mask[R]);
  return Secret(table[B][L], table[B][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 2652 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 110 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 2808 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 395 ms 4352 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 384 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 383 ms 4568 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 385 ms 4312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 388 ms 4404 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 382 ms 4432 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 386 ms 4344 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1