oj.uz

Submission #243481

# Submission time Handle Problem Language Result Execution time Memory
243481 2020-07-01T08:56:32 Z AlexPop28 Secret (JOI14_secret) C++11
100 / 100
 515 ms 4600 KB 
#include <bits/stdc++.h>
#include "secret.h"

using namespace std;

int logn, size;
vector<vector<int>> st;

void Init(int n, int a[]) {
  logn = 32 - __builtin_clz(n);
  size = 1 << logn;
  st.resize(logn, vector<int>(size));
  
  for (int i = 0; i < n; ++i) {
    st[0][i] = a[i];
  }
    
  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] = a[i - 1];
      for (int j = i - 2; j >= i - half; --j) {
        st[h][j] = Secret(a[j], st[h][j + 1]);
      }
      st[h][i] = a[i];
      for (int j = i + 1; j < i + half; ++j) {
        if (j < n)
          st[h][j] = Secret(st[h][j - 1], a[j]);
        else
          st[h][j] = st[h][j - 1];
      }
    }
  }
}

int Query(int l, int r) {
  if (l == r)
    return st[0][l];
    
  int h = 31 - __builtin_clz(l ^ r);
  return Secret(st[h][l], st[h][r]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2480 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 2552 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 148 ms 2552 KB Output is correct - number of calls to Secret by Init = 4097, maximum number of calls to Secret by Query = 1
4 Correct 508 ms 4396 KB Output is correct - number of calls to Secret by Init = 7979, maximum number of calls to Secret by Query = 1
5 Correct 515 ms 4500 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
6 Correct 509 ms 4600 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 4600 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
8 Correct 507 ms 4360 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
9 Correct 507 ms 4472 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1
10 Correct 508 ms 4472 KB Output is correct - number of calls to Secret by Init = 7986, maximum number of calls to Secret by Query = 1