oj.uz

Submission #938912

# Submission time Handle Problem Language Result Execution time Memory
938912 2024-03-05T19:47:15 Z PagodePaiva Secret (JOI14_secret) C++17
100 / 100
 387 ms 4456 KB 
#include "secret.h"
#include<bits/stdc++.h>
#define N 1010
#define LOGN 11

using namespace std;

int n;
int v[N];
int lt[N][LOGN], rt[N][LOGN];

void prep(int l, int r, int con){
  if(l == r) return;
  int mid = (l+r)/2;
  lt[mid][con] = v[mid];
  rt[mid+1][con] = v[mid+1];
  for(int i = mid-1;i >= l;i--){
    lt[i][con] = Secret(v[i], lt[i+1][con]);
  }
  for(int i = mid+2;i <= r;i++){
    rt[i][con] = Secret(rt[i-1][con], v[i]);
  }
  prep(l, mid, con+1);
  prep(mid+1, r, con+1);
  return;
}

int query(int l, int r, int tl = 0, int tr = n-1, int con = 0){
  if(tl == tr) return v[tl];
  int mid = (tl+tr)/2;
  if(l <= mid and mid < r) return Secret(lt[l][con], rt[r][con]);
  if(r <= mid) return query(l, r, tl, mid, con+1);
  // else return query(l, )
  return query(l, r, mid+1, tr, con+1);
}

void Init(int NN, int A[]) {
  n = NN;
  for(int i = 0;i < n;i++) v[i] = A[i];
  prep(0, n-1, 0);
  // Secret(0, 1000000000);
}

int Query(int L, int R) {
  return query(L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2732 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 107 ms 2732 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 2648 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 382 ms 4456 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 379 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 387 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 382 ms 4436 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 384 ms 4272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 379 ms 4268 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 384 ms 4272 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1