oj.uz

Submission #565968

# Submission time Handle Problem Language Result Execution time Memory
565968 2022-05-21T15:53:05 Z SSRS Secret (JOI14_secret) C++14
0 / 100
 444 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;
  int N;
  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 N2 = A.size();
    N = 1;
    int LOG = 0;
    while (N < N2){
      N *= 2;
      LOG++;
    }
    A.resize(N);
    for (int i = N2; i < N; i++){
      A[i] = -1;
    }
    D = vector<vector<T>>(LOG - 1, vector<T>(N, -1));
    for (int i = 0; i < LOG - 1; i++){
      for (int j = 0; j < N; j += 1 << (i + 2)){
        int d = 1 << (i + 1);
        D[i][j + d - 1] = A[j + d - 1];
        for (int k = j + d - 2; k >= j; k--){
          D[i][k] = f(A[k], D[i][k + 1]);
        }
        D[i][j + d] = A[j + d];
        for (int k = j + d + 1; k < j + d * 2; k++){
          D[i][k] = f(D[i][k - 1], A[k]);
        }
      }
    }
  }
  int query(int L, int R){
    if (R - L == 1){
      return A[L];
    } else {
      R--;
      int b = 30 - __builtin_clz(R ^ L);
      return f(D[b][L], D[b][R]);
    }
  }
};
int f(int a, int b){
  if (a == -1 || b == -1){
    return -1;
  }
  return Secret(a, b);
}
disjoint_sparse_table<int> DST;
void Init(int N, int A[]){
  vector<int> A2(N);
  for (int i = 0; i < N; i++){
    A2[i] = i;
  }
  DST = disjoint_sparse_table<int>(A2, f);
}
int Query(int L, int R){
  L--;
  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:61:41:   required from here
secret.cpp:8:13: warning: 'disjoint_sparse_table<int>::A' will be initialized after [-Wreorder]
    8 |   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:12:3: warning:   when initialized here [-Wreorder]
   12 |   disjoint_sparse_table(vector<T> &A, function<T(T, T)> f): A(A), f(f){
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 2508 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 272917235.
2 Incorrect 116 ms 2416 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 22118440.
3 Incorrect 114 ms 2380 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 763486228.
4 Incorrect 428 ms 4392 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 644416163.
5 Incorrect 422 ms 4368 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 507171604.
6 Incorrect 417 ms 4372 KB Wrong Answer: Query(915, 915) - expected : 282904741, actual : 914.
7 Incorrect 421 ms 4412 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 802757736.
8 Incorrect 444 ms 4344 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 612442448.
9 Incorrect 423 ms 4448 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 835854187.
10 Incorrect 426 ms 4404 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 806486094.