oj.uz

Submission #243498

# Submission time Handle Problem Language Result Execution time Memory
243498 2020-07-01T09:11:57 Z AlexPop28 Secret (JOI14_secret) C++11
100 / 100
 540 ms 4476 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

template<class T, class F = function<T(const T&, const T&)>>
struct SparseTable {
  int n;
  vector<vector<T>> st;
  F func;
  
  SparseTable() {}
  SparseTable(const vector<T> &v, const F &f) : n(v.size()), func(f) {
    int logn = 32 - __builtin_clz(n);
    st.resize(logn, vector<T>(n));
    st[0] = v;
    
    for (int h = 1; h < logn; ++h) {
      int half = 1 << h, full = 1 << (h + 1);
      for (int i = half; i < n; i += full) {
        st[h][i - 1] = v[i - 1];
        for (int j = i - 2; j >= i - half; --j) {
          st[h][j] = func(v[j], st[h][j + 1]);
        }
        st[h][i] = v[i];
        for (int j = i + 1; j < i + half && j < n; ++j) {
          st[h][j] = func(st[h][j - 1], v[j]);
        }
      }
    }
  }
  
  T Get(int l, int r) const {
    assert(0 <= l && l <= r && r < n);
    if (l == r) return st[0][l];
    int h = 31 - __builtin_clz(l ^ r);
    return func(st[h][l], st[h][r]);
  }
};


SparseTable<int> st;

void Init(int n, int a[]) {
  vector<int> v(n);
  for (int i = 0; i < n; ++i)
    v[i] = a[i];
    
  st = SparseTable<int>(v, [&](int a, int b) {
    return Secret(a, b);
  });
}

int Query(int l, int r) {
  return st.Get(l, r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2424 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 149 ms 2424 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 155 ms 2424 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 524 ms 4368 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 540 ms 4448 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
6 Correct 512 ms 4472 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
7 Correct 510 ms 4472 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
8 Correct 511 ms 4472 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
9 Correct 504 ms 4384 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
10 Correct 514 ms 4476 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1