제출 #647784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647784		dnx04	비밀 (JOI14_secret)	C++17	100 / 100	502 ms	8332 KiB

secret

#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 / 100