Submission #1076079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076079		MyCode	Secret (JOI14_secret)	C++17	100 / 100	343 ms	5572 KiB

secret

#include "secret.h"

#include <iostream>
#include <map>

using namespace std;

const int N = 1010;
const int H = 15;

map<pair<int, int>, int> f;

int nonSecret(int x, int y){
  if(f.find({x, y}) == f.end())
    f[{x, y}] = Secret(x, y);
  return f[{x, y}];
}

int lef[H][N], rig[H][N], a[N], cur_n;

void build(int v, int l, int r, int level){
  if(l == r){
      lef[level][l] = a[l], rig[level][r] = a[r];
      return;
  }
  int mid = (l + r) / 2;
  lef[level][mid] = a[mid];
  for(int i = mid - 1; i >= l; i--)
    lef[level][i] = nonSecret(a[i], lef[level][i + 1]);
  rig[level][mid + 1] = a[mid + 1];
  for(int i = mid + 2; i <= r; i++)
    rig[level][i] = nonSecret(rig[level][i - 1], a[i]);
  build(v * 2, l, mid, level + 1);
  build(v * 2 + 1, mid + 1, r, level + 1);
}

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

int get(int v, int l, int r, int tl, int tr, int level){
  int mid = (l + r) / 2;
  if(tl <= mid && tr > mid)
    return nonSecret(lef[level][tl], rig[level][tr]);
  if(tr <= mid) return get(v * 2, l, mid, tl, tr, level + 1);
  return get(v * 2 + 1, mid + 1, r, tl, tr, level + 1);
}

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

• Subtask 1: 100 / 100