oj.uz

답안 #256224

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256224 2020-08-02T11:37:49 Z islingr 비밀 (JOI14_secret) C++17
100 / 100
 518 ms 4656 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()));
  reverse(begin(L[v]), end(L[v]));
  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][lo - l], 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

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 2596 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 2680 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 2684 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 4600 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 518 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 512 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 514 ms 4604 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 4600 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 4656 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 508 ms 4600 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1