Submission #256228

#	Time	Username	Problem	Language	Result	Execution time	Memory
256228		islingr	Secret (JOI14_secret)	C++17	100 / 100	516 ms	4600 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a); )

const int N = 1 << 10;
vector<int> L[N << 1], R[N << 1], a;
int n;

void build(int v, int l, int r) {
  if (r - l == 1) return;
  int m = (l + r) >> 1;
  L[v] = {a[m - 1]}; per(i, l, m - 1) L[v].push_back(Secret(a[i], L[v].back()));
  R[v] = {a[m]}; rep(i, m + 1, r) R[v].push_back(Secret(R[v].back(), a[i]));
  build(v << 1|0, l, m); build(v << 1|1, m, r);
}

void Init(int N, int A[]) {
  n = N; a.resize(n); rep(i, 0, n) a[i] = A[i];
  build(1, 0, n);
}

int lo, hi;
int query(int v, int l, int r) {
  if (r - l == 1) return a[l];
  int m = (l + r) >> 1;
  if (hi <= m) return query(v << 1|0, l, m);
  if (m <= lo) return query(v << 1|1, m, r);
  return Secret(L[v][m - lo - 1], R[v][hi - m - 1]);
}

int Query(int L, int R) {
  lo = L; hi = R + 1;
  return query(1, 0, n);
}

• Subtask 1: 100 / 100