#include "brperm.h"
#include <iostream>
#define endl '\n'
using namespace std;
const int MAXN = 500000;
const int LOG = 20;
const int BASE = 26;
const int MOD = 1000000007;
int n;
int pw[MAXN + 1];
struct Hash
{
int len;
int num;
};
Hash operator + (Hash h1, Hash h2)
{
Hash ret;
ret.len = h1.len + h2.len;
ret.num = (1ll * h1.num * pw[h2.len] + h2.num) % MOD;
return ret;
}
bool operator == (Hash h1, Hash h2)
{
return (h1.len == h2.len and h1.num == h2.num);
}
Hash h1[MAXN + 1][LOG + 1];
Hash h2[MAXN + 1][LOG + 1];
void init(int n0, const char s[])
{
n = n0;
pw[0] = 1;
for (int i = 1; i <= MAXN; ++ i)
{
pw[i] = (1ll * pw[i - 1] * BASE) % MOD;
}
for (int i = 0; i < n; ++ i)
{
h1[i][0].len = 1;
h1[i][0].num = s[i] - 'a';
}
for (int j = 1; j <= LOG; ++ j)
{
for (int i = 0; i < n - (1ll << (j - 1)); ++ i)
{
h1[i][j] = h1[i][j - 1] + h1[i + (1ll << (j - 1))][j - 1];
}
}
for (int j = 0; j <= LOG; ++ j)
{
for (int i = 0; i < n; ++ i)
{
h2[i][j].len = 1;
h2[i][j].num = s[i] - 'a';
}
for (int k = j - 1; k >= 0; -- k)
{
for (int i = 0; i < n - (1ll << k); ++ i)
{
h2[i][j] = h2[i][j] + h2[i + (1ll << k)][j];
}
}
}
return;
}
int query(int pos, int k)
{
if (pos + (1ll << k) > n) return 0;
return (h1[pos][k] == h2[pos][k]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2508 KB |
Output is correct |
2 |
Correct |
5 ms |
2624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2508 KB |
Output is correct |
2 |
Correct |
5 ms |
2624 KB |
Output is correct |
3 |
Correct |
277 ms |
35828 KB |
Output is correct |
4 |
Correct |
315 ms |
35916 KB |
Output is correct |
5 |
Correct |
335 ms |
36008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1996 ms |
168664 KB |
Output is correct |
2 |
Correct |
1751 ms |
168572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2508 KB |
Output is correct |
2 |
Correct |
5 ms |
2624 KB |
Output is correct |
3 |
Correct |
277 ms |
35828 KB |
Output is correct |
4 |
Correct |
315 ms |
35916 KB |
Output is correct |
5 |
Correct |
335 ms |
36008 KB |
Output is correct |
6 |
Correct |
1996 ms |
168664 KB |
Output is correct |
7 |
Correct |
1751 ms |
168572 KB |
Output is correct |
8 |
Correct |
1770 ms |
168580 KB |
Output is correct |
9 |
Correct |
1971 ms |
168552 KB |
Output is correct |
10 |
Correct |
1892 ms |
168604 KB |
Output is correct |