oj.uz

Submission #308890

# Submission time Handle Problem Language Result Execution time Memory
308890 2020-10-02T07:16:43 Z syy Secret (JOI14_secret) C++17
100 / 100
 545 ms 8316 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 156 ms 4440 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 151 ms 4344 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 152 ms 4344 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 532 ms 8316 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 534 ms 8312 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 528 ms 8184 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 536 ms 8312 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 535 ms 8184 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 543 ms 8184 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 545 ms 8184 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1