oj.uz

Submission #384194

# Submission time Handle Problem Language Result Execution time Memory
384194 2021-03-31T17:47:10 Z faresbasbs Secret (JOI14_secret) C++14
100 / 100
 512 ms 8476 KB 
#include "secret.h"

#define MAX_N 1000

int range[MAX_N + 1][MAX_N + 1];

void Solve(int left, int right) {
  int mid, i;
  if (right - left <= 1) {
    return;
  }
  mid = (left + right) / 2;
  for (i = mid - 1; i >= left; --i) {
    if (range[i][mid] == -1) {
      range[i][mid] = Secret(range[i][i + 1], range[i + 1][mid]);
    }
  }
  for (i = mid + 1; i <= right; ++i) {
    if (range[mid][i] == -1) {
      range[mid][i] = Secret(range[mid][i - 1], range[i - 1][i]);
    }
  }
  Solve(left, mid);
  Solve(mid, right);
}

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

int Query(int L, int R) {
  int i;
  for (i = L + 1; i <= R; ++i) {
    if (range[L][i] != -1 && range[i][R + 1] != -1) {
      return Secret(range[L][i], range[i][R + 1]);
    }
  }
  return range[L][R + 1];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 4588 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 4460 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 509 ms 8428 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 505 ms 8428 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 506 ms 8476 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 511 ms 8320 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 512 ms 8428 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 510 ms 8300 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 510 ms 8428 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1