| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1001841 | Nelt | Dabbeh (INOI20_dabbeh) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 998244353, p = 37, lg = 20;
const ll N = 5e5 + 5;
ll pw[N], invpw[N];
ll up[lg][N];
ll binpow(ll n, ll p)
{
n %= mod;
ll ans = 1;
while (p)
{
ans = ans * (p & 1 ? n : 1) % mod;
p >>= 1;
n = n * n % mod;
}
return ans;
}
ll inv(ll n)
{
return binpow(n, mod - 2);
}
struct SegTree
{
vector<pair<ll, ll>> st;
ll n;
SegTree(ll sz = 0)
{
n = sz;
st.resize(n << 1, make_pair(0, 0));
}
void set(ll i, ll v)
{
st[i + n] = make_pair(v, i);
}
void build()
{
for (ll i = n - 1; i >= 1; i--) st[i] = max(st[i << 1], st[i << 1 | 1]);
}
pair<ll, ll> query(ll l, ll r)
{
pair<ll, ll> ans = make_pair(-1, -1);
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) ans = max(ans, st[l++]);
if (r & 1) ans = max(ans, st[--r]);
}
return ans;
}
};
void solve()
{
ll n, q;
cin >> n >> q;
string t[n];
for (string &i : t) cin >> i;
pw[0] = 1;
for (ll i = 1; i < N; i++) pw[i] = pw[i - 1] * p % mod;
for (ll i = 0; i < N; i++) invpw[i] = inv(pw[i]);
set<string> hs;
hs.insert("");
for (string x : t)
{
ll cur = 0;
for (ll j = 0; j < min(x.size(), s.size()); j++) cur = (cur + (x[j] - 'a' + 1) * pw[j]) % mod, hs.insert(x.substr(0, j + 1));
}
string s;
cin >> s;
ll pref[s.size()];
for (ll i = 0; i < s.size(); i++)
pref[i] = ((i - 1 < 0 ? 0 : pref[i - 1]) + (s[i] - 'a' + 1) * pw[i]) % mod;
auto gethash = [&](ll l, ll r)
{
return l > r ? 0 : (pref[r] - (l == 0 ? 0 : pref[l - 1]) + mod) % mod * invpw[l] % mod;
};
ll rig[s.size()];
for (ll i = 0; i < s.size(); i++)
{
ll l = i, r = s.size() - 1;
rig[i] = i;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (hs.count(s.substr(i, mid - i + 1))) rig[i] = mid + 1, l = mid + 1;
else r = mid - 1;
}
}
SegTree st(s.size() + 1);
for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
st.set(s.size(), s.size());
st.build();
for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
up[0][s.size()] = s.size();
for (ll bit = 1; bit < lg; bit++)
for (ll i = 0; i <= s.size(); i++) up[bit][i] = up[bit - 1][up[bit - 1][i]];
while (q--)
{
ll l, r;
cin >> l >> r;
ll ans = 0;
while (l < r)
{
if (rig[l] >= r)
{
ans++;
break;
}
if (l == up[0][l])
{
ans = -1;
break;
}
l = up[0][l], ans++;
}
cout << ans << endl;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll cs = 1; cs <= t; cs++)
solve();
// cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}