Submission #961411

#	Time	Username	Problem	Language	Result	Execution time	Memory
961411		aufan	Secret (JOI14_secret)	C++17	100 / 100	363 ms	9296 KiB

secret

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

using namespace std;

int n;
vector<int> a(1111);
vector<vector<int>> val(1111, vector<int>(1111, -1));

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

  function<void(int, int)> dnc = [&](int lf, int rg) {  
    if (rg - lf + 1 <= 2) return;

    int md = (lf + rg) / 2;
    for (int i = md - 1; i >= lf; i--) {
      if (val[i][md] == -1) {
        val[i][md] = Secret(a[i], val[i + 1][md]);
      }
    }
    for (int i = md + 2; i <= rg; i++) {
      if (val[md + 1][i] == -1) {
        val[md + 1][i] = Secret(val[md + 1][i - 1], a[i]);
      }
    }

    dnc(lf, md);
    dnc(md + 1, rg);
  };

  dnc(0, n - 1);
}

int Query(int l, int r) {
  function<int(int, int)> dnc = [&](int lf, int rg) {
    if (val[l][r] != -1) return val[l][r];

    int md = (lf + rg) / 2;
    if (l > md) {
      return dnc(md + 1, rg);
    } else if (r < md + 1) {
      return dnc(lf, md);
    } else {
      return Secret(val[l][md], val[md + 1][r]);
    }
  };

  return dnc(0, n - 1);
}

• Subtask 1: 100 / 100