oj.uz

Submission #1105820

# Submission time Handle Problem Language Result Execution time Memory
1105820 2024-10-28T02:45:44 Z ortsac Secret (JOI14_secret) C++17
100 / 100
 321 ms 5644 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3588 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 89 ms 3668 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 91 ms 3588 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 317 ms 5644 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 313 ms 5600 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 313 ms 5388 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 320 ms 5564 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 317 ms 5568 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 321 ms 5400 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 315 ms 5620 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1