Submission #757833

#	Time	Username	Problem	Language	Result	Execution time	Memory
757833		taher	Secret (JOI14_secret)	C++17	100 / 100	494 ms	36484 KiB

secret

#include <bits/stdc++.h>

#include "secret.h"

using namespace std;

const int MaxN = 1005;
const int inf = 1234567890;

vector<vector<int>> calcPrev(4 * MaxN, vector<int> (MaxN)), calcNext(4 * MaxN, vector<int> (MaxN));
vector<int> at(MaxN, inf);
int n;
vector<int> a(MaxN);

void Init(int N, int A[]) {
  n = N;
  for (int i = 0; i < n; i++) a[i] = A[i];
  function<void(int, int, int)> Divide = [&](int cnt, int low, int high) {
    if (low > high) {
      return ;
    }
    int mid = low + (high - low) / 2;
    int cur = a[mid];
    at[mid] = cnt;
    calcPrev[cnt][mid] = cur;
    for (int i = mid - 1; i >= low; i--)  {
      cur = Secret(a[i], cur);
      calcPrev[cnt][i] = cur;
    }
    if (mid < high) {
      cur = a[mid + 1];
      calcNext[cnt][mid + 1] = cur;
      for (int i = mid + 2; i <= high; i++) {
        cur = Secret(cur, a[i]);
        calcNext[cnt][i] = cur;
      }
    }
    Divide(2 * cnt, low, mid - 1);
    Divide(2 * cnt + 1, mid + 1, high);
    return ;
  };
  Divide(1, 0, n - 1);
}

int Query(int L, int R) {
  int l = L, r = R;
  int mnId = inf;
  int it = -1;
  for (int i = l; i <= r; i++) {
    if (mnId > at[i]) {
      it = i;
      mnId = at[i];
    }
  }
  int cur = calcPrev[mnId][l];
  if (r > it) {
    cur = Secret(cur, calcNext[mnId][r]);
  }
  return cur;
}

• Subtask 1: 100 / 100