oj.uz

Submission #256227

# Submission time Handle Problem Language Result Execution time Memory
256227 2020-08-02T11:39:37 Z islingr Secret (JOI14_secret) C++17
100 / 100
 517 ms 4616 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b); i-- > (a); )

const int N = 1 << 10;
vector<int> L[N << 1], R[N << 1], a;
int n;

void build(int v, int l, int r) {
  if (r - l == 1) return;
  int m = (l + r) >> 1;
  L[v] = {a[m - 1]}; per(i, l, m - 1) L[v].push_back(Secret(a[i], L[v].back()));
  R[v] = {a[m]}; rep(i, m + 1, r) R[v].push_back(Secret(R[v].back(), a[i]));
  build(v << 1|0, l, m); build(v << 1|1, m, r);
}

void Init(int N, int A[]) {
  n = N; a.resize(n); rep(i, 0, n) a[i] = A[i];
  build(1, 0, n);
}

int lo, hi;
int query(int v, int l, int r) {
  if (r - l == 1) return a[l];
  int m = (l + r) >> 1;
  assert(l <= lo && hi <= r);
  if (hi <= m) return query(v << 1|0, l, m);
  if (m <= lo) return query(v << 1|1, m, r);
  return Secret(L[v][m - lo - 1], R[v][hi - m - 1]);
}

int Query(int L, int R) {
  lo = L; hi = R + 1;
  return query(1, 0, n);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2556 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 2552 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 2556 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 513 ms 4472 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 504 ms 4500 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 511 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 516 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 509 ms 4476 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 517 ms 4616 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 514 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1