oj.uz

Submission #401723

# Submission time Handle Problem Language Result Execution time Memory
401723 2021-05-10T18:11:39 Z rama_pang Brperm (RMI20_brperm) C++17
100 / 100
 453 ms 76684 KB 
#include "brperm.h"

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 500005;
const int LOG = 19;

// Solution:
// B = Base
// StraightHash(B, L, K) = \sum_{i = L}^{L + 2^K - 1} B^{i - L} x_i
// BrPermHash(B, L, K) = BrPermHash(B^2, L, K - 1) + B * BrPermHash(B^2, L + 2^{K - 1}, K - 1)

int N;
string S;

int Base[LOG];
int BrPermHash[MAX][LOG];
int StraightHash[MAX][LOG];

void init(int n, const char s[]) {
  N = n, S = s;

  Base[LOG - 1] = 37;
  for (int i = LOG - 2; i >= 0; i--) {
    Base[i] = 1ll * Base[i + 1] * Base[i + 1] % MOD;
  }

  for (int L = N - 1; L >= 0; L--) {
    BrPermHash[L][0] = (S[L] - 'a' + 1);
    for (int K = 1; K < LOG; K++) {
      BrPermHash[L][K] = BrPermHash[L][K - 1];
      if (L + (1 << (K - 1)) <= N) {
        BrPermHash[L][K] += 1ll * Base[K] * BrPermHash[L + (1 << (K - 1))][K - 1] % MOD;
        BrPermHash[L][K] %= MOD;
      }
    }
  }

  for (int L = N - 1; L >= 0; L--) {
    for (int K = 0; K < LOG; K++) {
      StraightHash[L][K] = ((S[L] - 'a' + 1) + 1ll * Base[K] * StraightHash[L + 1][K]) % MOD;
    }
  }

  for (int K = 0; K < LOG; K++) {
    int power = 1;
    for (int i = 0; i < (1 << K); i++) {
      power = 1ll * power * Base[K] % MOD;
    }
    for (int L = 0; L < N; L++) {
      if (L + (1 << K) <= N) {
        StraightHash[L][K] += MOD - (1ll * power * StraightHash[L + (1 << K)][K] % MOD);
        StraightHash[L][K] %= MOD;
      }
    }
  }
}

int query(int i, int k) {
  return (i + (1 << k) <= N) && StraightHash[i][k] == BrPermHash[i][k];
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 476 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 476 KB Output is correct
3 Correct 71 ms 15464 KB Output is correct
4 Correct 70 ms 15504 KB Output is correct
5 Correct 74 ms 15504 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 76684 KB Output is correct
2 Correct 417 ms 76680 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 476 KB Output is correct
3 Correct 71 ms 15464 KB Output is correct
4 Correct 70 ms 15504 KB Output is correct
5 Correct 74 ms 15504 KB Output is correct
6 Correct 453 ms 76684 KB Output is correct
7 Correct 417 ms 76680 KB Output is correct
8 Correct 411 ms 76588 KB Output is correct
9 Correct 416 ms 76576 KB Output is correct
10 Correct 413 ms 76556 KB Output is correct