oj.uz

Submission #989156

# Submission time Handle Problem Language Result Execution time Memory
989156 2024-05-27T15:53:30 Z aykhn Secret (JOI14_secret) C++17
100 / 100
 323 ms 4440 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;
int val[15][1005];
int a[1005];

void build(int l, int r, int d)
{
  if (l >= r) return;
  int mid = (l + r) >> 1;
  val[d][mid] = a[mid];
  val[d][mid + 1] = a[mid + 1];
  for (int i = mid - 1; i >= l; i--) val[d][i] = Secret(a[i], val[d][i + 1]);
  for (int i = mid + 2; i <= r; i++) val[d][i] = Secret(val[d][i - 1], a[i]);
  build(l, mid - 1, d + 1);
  build(mid + 2, r, d + 1);
}

void Init(int N, int A[]) 
{
  n = N;
  for (int i = 0; i < N; i++) a[i] = A[i];
  build(0, N - 1, 0);
}

int get(int l, int r, int d, int lx, int rx)
{
  if (!(l <= lx && r >= rx)) return -1;
  if (l >= r) assert(0);
  int mid = (l + r) >> 1;
  int x = get(l, mid - 1, d + 1, lx, rx);
  if (x != -1) return x;
  x = get(mid + 2, r, d + 1, lx, rx);
  if (x != -1) return x;
  if (lx > mid) return val[d][rx];
  if (rx <= mid) return val[d][lx];
  return Secret(val[d][lx], val[d][rx]);
}

int Query(int L, int R) 
{
  if (L == R) return a[L];
  return get(0, n - 1, 0, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2732 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 84 ms 2736 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 101 ms 2732 KB Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4 Correct 295 ms 4224 KB Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5 Correct 311 ms 4436 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6 Correct 295 ms 4432 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7 Correct 318 ms 4436 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 308 ms 4436 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 323 ms 4440 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 293 ms 4436 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1