oj.uz

Submission #646146

# Submission time Handle Problem Language Result Execution time Memory
646146 2022-09-28T19:16:36 Z Alex_tz307 Brperm (RMI20_brperm) C++17
100 / 100
 495 ms 163404 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 len, int k, int t) {
  return add(hsh[t][i][k], mod[t] - mult(hsh[t][i + len][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][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, 1 << k, kLog - k, 0) == brHash[0][i][k] && getHsh(i, 1 << k, kLog - 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 90 ms 32844 KB Output is correct
4 Correct 89 ms 32748 KB Output is correct
5 Correct 97 ms 32840 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 162852 KB Output is correct
2 Correct 475 ms 163404 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 90 ms 32844 KB Output is correct
4 Correct 89 ms 32748 KB Output is correct
5 Correct 97 ms 32840 KB Output is correct
6 Correct 495 ms 162852 KB Output is correct
7 Correct 475 ms 163404 KB Output is correct
8 Correct 491 ms 163296 KB Output is correct
9 Correct 480 ms 163216 KB Output is correct
10 Correct 472 ms 163404 KB Output is correct