oj.uz

Submission #647784

# Submission time Handle Problem Language Result Execution time Memory
647784 2022-10-04T06:21:08 Z dnx04 Secret (JOI14_secret) C++17
100 / 100
 502 ms 8332 KB 
#include "secret.h"

const int N = 1000;
int res[N][N], n;

void precompute(int l, int r, int a[]) {
  int mid = (l + r) / 2;
  res[mid][mid] = a[mid];
  res[mid + 1][mid + 1] = a[mid + 1];
  for (int i = mid + 2; i <= r; ++i)
    res[mid + 1][i] = Secret(res[mid + 1][i - 1], a[i]);
  for (int i = mid - 1; i >= l; --i)
    res[mid][i] = Secret(a[i], res[mid][i + 1]);
  if (l < mid) precompute(l, mid, a);
  if (mid + 1 < r) precompute(mid + 1, r, a);
}

void Init(int N, int A[]) {
  n = N;
  precompute(0, n - 1, A);
}

int Query(int L, int R) {
  int a = 0, b = n - 1;
  while (a != b) {
    int mid = (a + b) / 2;
    if (mid >= L && mid < R)
      return Secret(res[mid][L], res[mid + 1][R]);
    else if (mid == R)
      return res[mid][L];
    else if (mid < L)
      a = mid + 1;
    else
      b = mid;
  }
  return res[a][a];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 4396 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 128 ms 4476 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 136 ms 4452 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 450 ms 8244 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 467 ms 8144 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 455 ms 8332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 461 ms 8236 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 478 ms 8264 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 502 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 450 ms 8196 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1