oj.uz

Submission #646148

# Submission time Handle Problem Language Result Execution time Memory
646148 2022-09-28T19:18:59 Z Alex_tz307 Brperm (RMI20_brperm) C++17
100 / 100
 512 ms 158488 KB 
#include <bits/stdc++.h>
#include "brperm.h"
 
using namespace std;
 
const int kN = 5e5;
const int kLog = 19;
const int base[] = {29, 31};
const int mod[] = {(int)1e9 + 7, (int)1e9 + 9};
int N, p[2][1 + kLog];
int hsh[2][1 + kN + 1][1 + kLog];
int brHash[2][1 + kN][1 + kLog];
 
int add(int x, int y, int mod) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
  return x;
}
 
int mult(int x, int y, int mod) {
  return (int64_t)x * y % mod;
}
 
int getHsh(int i, int k, int t) {
  return add(hsh[t][i][k], mod[t] - mult(hsh[t][i + (1 << k)][k], p[t][kLog], mod[t]), mod[t]);
}
 
void init(int n, const char s[]) {
  N = n;
 
  for (int i = 0; i < 2; ++i) {
    p[i][0] = base[i];
  }
  for (int k = 1; k <= kLog; ++k) {
    for (int i = 0; i < 2; ++i) {
      p[i][k] = mult(p[i][k - 1], p[i][k - 1], mod[i]);
    }
  }
 
  for (int k = 0; k <= kLog; ++k) {
    for (int i = n; i > 0; --i) {
      for (int j = 0; j < 2; ++j) {
        hsh[j][i][k] = add(mult(hsh[j][i + 1][k], p[j][kLog - k], mod[j]), s[i - 1] - 'a' + 1, mod[j]);
      }
    }
  }
 
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 2; ++j) {
      brHash[j][i][0] = s[i - 1] - 'a' + 1;
    }
  }
  for (int k = 1; k <= kLog; ++k) {
    for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
      for (int j = 0; j < 2; ++j) {
        brHash[j][i][k] = add(brHash[j][i][k - 1], mult(p[j][kLog - k], brHash[j][i + (1 << (k - 1))][k - 1], mod[j]), mod[j]);
      }
    }
  }
 
}
 
int query(int i, int k) {
  i += 1;
  if (k >= 20 || i + (1 << k) - 1 > N) {
    return 0;
  }
  return getHsh(i, k, 0) == brHash[0][i][k] && getHsh(i, k, 1) == brHash[1][i][k];
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 91 ms 31832 KB Output is correct
4 Correct 92 ms 31924 KB Output is correct
5 Correct 94 ms 31928 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 158308 KB Output is correct
2 Correct 479 ms 158412 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 91 ms 31832 KB Output is correct
4 Correct 92 ms 31924 KB Output is correct
5 Correct 94 ms 31928 KB Output is correct
6 Correct 478 ms 158308 KB Output is correct
7 Correct 479 ms 158412 KB Output is correct
8 Correct 512 ms 158488 KB Output is correct
9 Correct 473 ms 158452 KB Output is correct
10 Correct 474 ms 158416 KB Output is correct