oj.uz

답안 #566079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566079 2022-05-21T18:12:58 Z SSRS 비밀 (JOI14_secret) C++14
100 / 100
 441 ms 4448 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
template <typename T>
struct disjoint_sparse_table{
  function<T(T, T)> f;
  vector<T> A;
  vector<vector<T>> D;
  disjoint_sparse_table(){
  }
  disjoint_sparse_table(vector<T> &A, function<T(T, T)> f): A(A), f(f){
    int N = A.size();
    int LOG = 32 - __builtin_clz(N - 1);
    D = vector<vector<T>>(LOG, vector<T>(N));
    for (int i = 0; i < LOG; i++){
      int d = 1 << i;
      for (int j = 0; j + d < N; j += d * 2){
        D[i][j + d - 1] = A[j + d - 1];
        for (int k = j + d - 2; k >= j; k--){
          if (k == j + (d >> 1)){
            D[i][k] = D[i - 1][j + d - 1];
          } else {
            D[i][k] = f(A[k], D[i][k + 1]);
          }
        }
        D[i][j + d] = A[j + d];
        for (int k = j + d + 1; k < min(j + d * 2, N); k++){
          if (k == j + d + (d >> 1) - 1){
            D[i][k] = D[i - 1][j + d];
          } else {
            D[i][k] = f(D[i][k - 1], A[k]);
          }
        }
      }
    }
  }
  T query(int L, int R){
    if (R - L == 1){
      return A[L];
    } else {
      R--;
      int b = 31 - __builtin_clz(R ^ L);
      return f(D[b][L], D[b][R]);
    }
  }
};
disjoint_sparse_table<int> DST;
void Init(int N, int A[]){
  vector<int> A2(N);
  for (int i = 0; i < N; i++){
    A2[i] = A[i];
  }
  DST = disjoint_sparse_table<int>(A2, Secret);
}
int Query(int L, int R){
  R++;
  return DST.query(L, R);
}

Compilation message

secret.cpp: In instantiation of 'disjoint_sparse_table<T>::disjoint_sparse_table(std::vector<_Tp>&, std::function<T(T, T)>) [with T = int]':
secret.cpp:53:46:   required from here
secret.cpp:7:13: warning: 'disjoint_sparse_table<int>::A' will be initialized after [-Wreorder]
    7 |   vector<T> A;
      |             ^
secret.cpp:6:21: warning:   'std::function<int(int, int)> disjoint_sparse_table<int>::f' [-Wreorder]
    6 |   function<T(T, T)> f;
      |                     ^
secret.cpp:11:3: warning:   when initialized here [-Wreorder]
   11 |   disjoint_sparse_table(vector<T> &A, function<T(T, T)> f): A(A), f(f){
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 2368 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 124 ms 2392 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 124 ms 2396 KB Output is correct - number of calls to Secret by Init = 3842, maximum number of calls to Secret by Query = 1
4 Correct 430 ms 4324 KB Output is correct - number of calls to Secret by Init = 7482, maximum number of calls to Secret by Query = 1
5 Correct 441 ms 4316 KB Output is correct - number of calls to Secret by Init = 7489, maximum number of calls to Secret by Query = 1
6 Correct 431 ms 4328 KB Output is correct - number of calls to Secret by Init = 7489, maximum number of calls to Secret by Query = 1
7 Correct 425 ms 4312 KB Output is correct - number of calls to Secret by Init = 7489, maximum number of calls to Secret by Query = 1
8 Correct 429 ms 4448 KB Output is correct - number of calls to Secret by Init = 7489, maximum number of calls to Secret by Query = 1
9 Correct 431 ms 4400 KB Output is correct - number of calls to Secret by Init = 7489, maximum number of calls to Secret by Query = 1
10 Correct 435 ms 4300 KB Output is correct - number of calls to Secret by Init = 7489, maximum number of calls to Secret by Query = 1