Submission #1105820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105820		ortsac	Secret (JOI14_secret)	C++17	100 / 100	321 ms	5644 KiB

secret

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

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

struct R {
  int val = -1;
};

int n;
vector<int> v;
map<pii, R> me;

int s(int a, int b) {
  if (me[{a, b}].val == -1) me[{a, b}].val = Secret(a, b);
  return me[{a, b}].val;
}

const int MAXN = 1010;
int res[11][MAXN];

void calc(int c, int l, int r) {
  if (l == r) return;
  int m = (l+r)/2;
  res[c][m] = v[m];
  for (int i = m - 1; i >= l; i--) {
    res[c][i] = s(v[i], res[c][i + 1]);
  }
  res[c][m + 1] = v[m + 1];
  for (int i = m + 2; i <= r; i++) {
    res[c][i] = s(res[c][i - 1], v[i]);
  }
  calc(c + 1, l, m);
  calc(c + 1, m + 1, r); 
}

int ans(int c, int l, int r, int tl, int tr) {
  int m = (l+r)/2;
  //cout << l << " " << r << " " << m << "\n";
  if (tr == m) {
    return res[c][tl];
  }
  if (tl == (m + 1)) {
    return res[c][tr];
  }
  if ((tl <= m) && (m < tr)) {
    //cout << res[c][tl] << " " << res[c][tr] << "\n";
    return s(res[c][tl], res[c][tr]);
  }
  if (tr < m) return ans(c + 1, l, m, tl, tr);
  return ans(c + 1, m + 1, r, tl, tr);
}

void Init(int N, int A[]) {
  //cout << s(5, s(8, s(3, 6))) << "\n";
  n = N;
  v.resize(n);
  for (int i = 0; i < n; i++) v[i] = A[i];
  calc(0, 0, n - 1);
}

int Query(int L, int R) {
  //for (int i = 0; i < n; i++) {
  //  //cout << v[i] << "\n";
  //}
  if (L == R) return v[L];
  return ans(0, 0, n - 1, L, R);
}

• Subtask 1: 100 / 100