oj.uz

Submission #954846

# Submission time Handle Problem Language Result Execution time Memory
954846 2024-03-28T17:14:06 Z evenvalue Secret (JOI14_secret) C++17
100 / 100
 363 ms 8276 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

int n;
array<array<int, 1000>, 1000> ans;

void Init(int N, int A[]) {
  n = N;

  function<void(int, int)> dnc = [&](const int l, const int r) {
    if (l == r) {
      ans[l][r] = A[l];
      return;
    }
    const int mid = (l + r) / 2;
    dnc(l, mid);
    dnc(mid + 1, r);
    for (int i = mid - 1; i >= l; i--) {
      ans[i][mid] = Secret(ans[i][i], ans[i + 1][mid]);
    }
    for (int i = mid + 2; i <= r; i++) {
      ans[mid + 1][i] = Secret(ans[mid + 1][i - 1], ans[i][i]);
    }
  };

  dnc(0, n - 1);
}

int Query(int L, int R) {
  if (L == R) return ans[L][R];
  int l = 0, r = n - 1;
  while (l < r) {
    const int mid = (l + r) / 2;
    if (R <= mid) {
      r = mid;
    } else if (mid < L) {
      l = mid + 1;
    } else {
      return Secret(ans[L][mid], ans[mid + 1][R]);
    }
  }
  assert(false);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 6740 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 102 ms 6740 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 102 ms 6736 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 357 ms 8276 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 360 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 359 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 360 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 363 ms 8256 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 361 ms 8272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 362 ms 8276 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1