#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F
const int MXN = 3e5 + 5;
const int mod = 1e9 + 7;
const int base = 1031;
int st[MXN << 2];
int lz[MXN << 2];
void relax(int l, int r, int x)
{
if (!lz[x]) return;
st[x] = (r - l + 1);
lz[x] = 0;
if (l == r) return;
lz[2*x] = lz[2*x + 1] = 1;
}
void make(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] = 1;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
make(l, mid, 2*x, lx, rx);
make(mid + 1, r, 2*x + 1, lx, rx);
st[x] = st[2*x] + st[2*x + 1];
}
int get(int l, int r, int x, int lx, int rx)
{
if (l > rx || r < lx) return 0;
relax(l, r, x);
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
}
int add(int a, int b)
{
return (a + b + mod) % mod;
}
int mult(int a, int b)
{
return (a * b) % mod;
}
int pw(int a, int b, int c)
{
a %= c;
int res = 1;
while (b)
{
if (b & 1) res = mult(res, a);
a = mult(a, a);
b >>= 1;
}
return res;
}
int ph[MXN], p[MXN], invp[MXN];
int get_hash(int l, int r)
{
return mult(add(ph[r], -ph[l - 1]), invp[l]);
}
void _HASH(string &s)
{
for (int i = 1; i < s.length(); i++)
{
ph[i] = add(ph[i - 1], mult(p[i], s[i] - 'a' + 1));
}
}
map<int, int> mp;
int R[MXN];
int ans[MXN];
vector<array<int, 2>> q[MXN];
int inter(array<int, 2> x, array<int, 2> y)
{
return max(x[0], y[0]) <= min(x[1], y[1]);
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
p[0] = 1, invp[0] = 1;
for (int i = 1; i < MXN; i++)
{
p[i] = mult(p[i - 1], base);
invp[i] = pw(p[i], mod - 2, mod);
}
int k, m;
cin >> k >> m;
string t[k];
for (int i = 0; i < k; i++) cin >> t[i];
string s;
cin >> s;
int n = s.length();
s = "#" + s;
_HASH(s);
for (int i = 0; i < k; i++)
{
int h = 0;
for (int j = 0; j < t[i].length(); j++)
{
h = add(h, mult(t[i][j] - 'a' + 1, p[j]));
mp[h] = 1;
}
}
for (int i = 1; i <= n; i++)
{
int l = i, r = n;
if (!mp[get_hash(i, i)])
{
continue;
}
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (mp[get_hash(i, mid)]) l = mid;
else r = mid - 1;
}
R[i] = l;
}
for (int i = 0; i < m; i++)
{
int l, r;
cin >> l >> r;
l++;
q[l].push_back({r, i});
}
vector<array<int, 2>> v;
for (int i = n; i >= 1; i--)
{
if (R[i])
{
make(1, n, 1, i, R[i]);
while (!v.empty())
{
if (v.back()[1] <= R[i]) v.pop_back();
else if (v.size() > 1 && inter(*prev(prev(v.end())), {i, R[i]})) v.pop_back();
else break;
}
v.push_back({i, R[i]});
}
for (array<int, 2> &j : q[i])
{
if (get(1, n, 1, i, j[0]) != j[0] - i + 1)
{
ans[j[1]] = -1;
continue;
}
int l = 0, r = (int)v.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (v[mid][1] >= j[0]) l = mid;
else r = mid - 1;
}
ans[j[1]] = (int)v.size() - l;
}
}
for (int i = 0; i < m; i++) cout << ans[i] << '\n';
}
Compilation message
Main.cpp: In function 'void _HASH(std::string&)':
Main.cpp:77:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 1; i < s.length(); i++)
| ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:114:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for (int j = 0; j < t[i].length(); j++)
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
13360 KB |
Output is correct |
| 2 |
Incorrect |
262 ms |
49236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2071 ms |
180104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
13360 KB |
Output is correct |
| 2 |
Incorrect |
262 ms |
49236 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
