oj.uz

Submission #1076079

# Submission time Handle Problem Language Result Execution time Memory
1076079 2024-08-26T11:01:59 Z MyCode Secret (JOI14_secret) C++17
100 / 100
 343 ms 5572 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 3412 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 92 ms 3412 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 92 ms 3420 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 328 ms 5500 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 343 ms 5456 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 322 ms 5456 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 323 ms 5572 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 323 ms 5460 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 325 ms 5524 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 322 ms 5460 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1