oj.uz

Submission #793471

# Submission time Handle Problem Language Result Execution time Memory
793471 2023-07-25T22:02:25 Z asdfgrace Secret (JOI14_secret) C++17
100 / 100
 369 ms 4680 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
 
int n;
vector<int> a;
vector<vector<int>> lef, rig;
 
void Init(int N, int A[]) {
  n = N;
  a.resize(N);
  for (int i = 0; i < N; ++i) a[i] = A[i];
  lef.resize(N); rig.resize(N);
  queue<pair<int, int>> q;
  q.push({0, n - 1});
  while (!q.empty()) {
    int l = q.front().first, r = q.front().second;
    q.pop();
    int m = (l + r) / 2;
    lef[m].push_back(A[m]);
    for (int i = 1; i <= (m - l); ++i) {
      lef[m].push_back(Secret(A[m - i], lef[m].back()));
    }
    if (m + 1 < N) {
      rig[m].push_back(A[m + 1]);
      for (int i = 2; i <= (r - m); ++i) {
        rig[m].push_back(Secret(rig[m].back(), A[m + i]));
      }
    }
    if (l == r) continue;
    q.push({l, m});
    q.push({m + 1, r});
  }
}
 
int Query(int L, int R) {
  if (L == R) return a[L];
  int l = 0, r = n - 1;
  while (true) {
    int m = (l + r) / 2;
    if (R <= m) {
      r = m;
    } else if (L > m) {
      l = m + 1;
    } else {
      return Secret(lef[m][m - L], rig[m][R - m - 1]);
    }
  }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 2508 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 108 ms 2616 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 103 ms 2548 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 363 ms 4452 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 365 ms 4532 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 4516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 366 ms 4680 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 365 ms 4428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 365 ms 4572 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 369 ms 4456 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1