제출 #1209703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209703		thecyb	비밀 (JOI14_secret)	C++17	0 / 100	397 ms	4560 KiB

secret

#include "secret.h"

int pfx[1000][1000], n;

void dnc(int l, int r, const int val[]) {
  int m = (l + r) >> 1;
  pfx[m][m] = val[m];
  pfx[m + 1][m + 1] = val[m + 1];
  for (int i = m - 1; i; i--)
    pfx[m][i] = Secret(val[i], pfx[m][i + 1]);
  for (int i = m + 2; i < n; i++)
    pfx[m + 1][i] = Secret(pfx[m + 1][i - 1], val[i]);
  if (l < m)
    dnc(l, m, val);
  if (m + 1 < r)
    dnc(m + 1, r, val);
}

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

int Query(int L, int R) {
  int u = 0, v = n - 1;
  while (u < v) {
    int m = (u + v) >> 1;
    if (m >= L && m < R)
      return Secret(pfx[m][L], pfx[m + 1][R]);
    if (m == R)
      return pfx[m][L];
    if (m < L)
      u = m + 1;
    else
      v = m;
  }
  return pfx[u][u];
}

• Subtask 1: 0 / 100