Submission #989156

#	Time	Username	Problem	Language	Result	Execution time	Memory
989156		aykhn	Secret (JOI14_secret)	C++17	100 / 100	323 ms	4440 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;
int val[15][1005];
int a[1005];

void build(int l, int r, int d)
{
  if (l >= r) return;
  int mid = (l + r) >> 1;
  val[d][mid] = a[mid];
  val[d][mid + 1] = a[mid + 1];
  for (int i = mid - 1; i >= l; i--) val[d][i] = Secret(a[i], val[d][i + 1]);
  for (int i = mid + 2; i <= r; i++) val[d][i] = Secret(val[d][i - 1], a[i]);
  build(l, mid - 1, d + 1);
  build(mid + 2, r, d + 1);
}

void Init(int N, int A[]) 
{
  n = N;
  for (int i = 0; i < N; i++) a[i] = A[i];
  build(0, N - 1, 0);
}

int get(int l, int r, int d, int lx, int rx)
{
  if (!(l <= lx && r >= rx)) return -1;
  if (l >= r) assert(0);
  int mid = (l + r) >> 1;
  int x = get(l, mid - 1, d + 1, lx, rx);
  if (x != -1) return x;
  x = get(mid + 2, r, d + 1, lx, rx);
  if (x != -1) return x;
  if (lx > mid) return val[d][rx];
  if (rx <= mid) return val[d][lx];
  return Secret(val[d][lx], val[d][rx]);
}

int Query(int L, int R) 
{
  if (L == R) return a[L];
  return get(0, n - 1, 0, L, R);
}

• Subtask 1: 100 / 100