| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002012 |
2024-06-19T09:12:47 Z |
vjudge1 |
Dabbeh (INOI20_dabbeh) |
C++17 |
|
0 ms |
0 KB |
#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 p = 37, lg = 20;
const ll N = 5e5 + 5;
ll mod[] = {998244353, (ll)1e9 + 9};
ll pw[3][N], invpw[3][N];
ll up[lg][N];
ll binpow(ll n, ll p, ll mod)
{
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, ll mod)
{
return binpow(n, mod - 2, mod);
}
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;
}
};
ll pref[2][N];
array<ll, 2> gethash(ll l, ll r)
{
if (l > r) return array<ll, 2>{0, 0};
array<ll, 2> ans = {0, 0};
for (ll i = 0; i < 2; i++)
ans[i] = (pref[i][r] - (l - 1 < 0 ? 0 : pref[i][l - 1]) + mod[i]) % mod[i] * invpw[i][l] % mod[i];
return ans;
}
void solve()
{
ll n, q;
cin >> n >> q;
string t[n];
for (string &i : t) cin >> i;
for (ll x = 0; x < 2; x++) pw[x][0] = invpw[x][0] = 1;
for (ll x = 0; x < 2; x++)
{
ll invp = inv(p, mod[x]);
for (ll i = 1; i < N; i++) pw[x][i] = pw[x][i - 1] * p % mod[x];
for (ll i = 1; i < N; i++) invpw[x][i] = invpw[x][i - 1] * invp % mod[x];
}
set<array<ll, 2>> hs;
hs.insert({0, 0});
string s;
cin >> s;
for (string e : t)
{
array<ll, 2> cur = {0, 0};
for (ll j = 0; j < e.size(); j++)
{
for (ll x = 0; x < 2; x++)
cur[x] = (cur[x] + (e[j] - 'a' + 1) * pw[x][j]) % mod[x];
hs.insert(cur);
}
}
for (ll x = 0; x < 2; x++)
for (ll i = 0; i < s.size(); i++)
pref[x][i] = ((i - 1 < 0 ? 0 : pref[x][i - 1]) + (s[i] - 'a' + 1) * pw[x][i]) % mod[x];
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(gethash(i, mid))) 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;
if (rig[l] >= r) cout << "1\n";
else
{
ll ans = 1;
for (ll bit = lg - 1; bit >= 0; bit--) if (rig[up[bit][l]] < r) ans += 1 << bit, l = up[bit][l];
if (rig[up[0][l]] < r) ans = -1;
else 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";
}#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 p = 37, lg = 20;
const ll N = 5e5 + 5;
ll mod[] = {998244353, (ll)1e9 + 9};
ll pw[3][N], invpw[3][N];
ll up[lg][N];
ll binpow(ll n, ll p, ll mod)
{
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, ll mod)
{
return binpow(n, mod - 2, mod);
}
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;
}
};
ll pref[2][N];
array<ll, 2> gethash(ll l, ll r)
{
if (l > r) return array<ll, 2>{0, 0};
array<ll, 2> ans = {0, 0};
for (ll i = 0; i < 2; i++)
ans[i] = (pref[i][r] - (l - 1 < 0 ? 0 : pref[i][l - 1]) + mod[i]) % mod[i] * invpw[i][l] % mod[i];
return ans;
}
void solve()
{
ll n, q;
cin >> n >> q;
string t[n];
for (string &i : t) cin >> i;
for (ll x = 0; x < 2; x++) pw[x][0] = invpw[x][0] = 1;
for (ll x = 0; x < 2; x++)
{
ll invp = inv(p, mod[x]);
for (ll i = 1; i < N; i++) pw[x][i] = pw[x][i - 1] * p % mod[x];
for (ll i = 1; i < N; i++) invpw[x][i] = invpw[x][i - 1] * invp % mod[x];
}
set<array<ll, 2>> hs;
hs.insert({0, 0});
string s;
cin >> s;
for (string e : t)
{
array<ll, 2> cur = {0, 0};
for (ll j = 0; j < e.size(); j++)
{
for (ll x = 0; x < 2; x++)
cur[x] = (cur[x] + (e[j] - 'a' + 1) * pw[x][j]) % mod[x];
hs.insert(cur);
}
}
for (ll x = 0; x < 2; x++)
for (ll i = 0; i < s.size(); i++)
pref[x][i] = ((i - 1 < 0 ? 0 : pref[x][i - 1]) + (s[i] - 'a' + 1) * pw[x][i]) % mod[x];
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(gethash(i, mid))) 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;
if (rig[l] >= r) cout << "1\n";
else
{
ll ans = 1;
for (ll bit = lg - 1; bit >= 0; bit--) if (rig[up[bit][l]] < r) ans += 1 << bit, l = up[bit][l];
if (rig[up[0][l]] < r) ans = -1;
else 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";
}
Compilation message
Main.cpp:145:2: error: stray '#' in program
145 | }#include <bits/stdc++.h>
| ^
Main.cpp: In function 'void solve()':
Main.cpp:89:26: 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]
89 | for (ll j = 0; j < e.size(); j++)
| ~~^~~~~~~~~~
Main.cpp:97:22: 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]
97 | for (ll i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
Main.cpp:100:22: 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]
100 | for (ll i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
Main.cpp:112:22: 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]
112 | for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
| ~~^~~~~~~~~~
Main.cpp:115:22: 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]
115 | for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
| ~~^~~~~~~~~~
Main.cpp:118:26: 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]
118 | for (ll i = 0; i <= s.size(); i++) up[bit][i] = up[bit - 1][up[bit - 1][i]];
| ~~^~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:145:3: error: 'include' does not name a type
145 | }#include <bits/stdc++.h>
| ^~~~~~~
Main.cpp:153:9: error: redefinition of 'std::mt19937 rng'
153 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
| ^~~
Main.cpp:9:9: note: 'std::mt19937 rng' previously declared here
9 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
| ^~~
Main.cpp:155:10: error: redefinition of 'const long long int p'
155 | const ll p = 37, lg = 20;
| ^
Main.cpp:11:10: note: 'const long long int p' previously defined here
11 | const ll p = 37, lg = 20;
| ^
Main.cpp:155:18: error: redefinition of 'const long long int lg'
155 | const ll p = 37, lg = 20;
| ^~
Main.cpp:11:18: note: 'const long long int lg' previously defined here
11 | const ll p = 37, lg = 20;
| ^~
Main.cpp:156:10: error: redefinition of 'const long long int N'
156 | const ll N = 5e5 + 5;
| ^
Main.cpp:12:10: note: 'const long long int N' previously defined here
12 | const ll N = 5e5 + 5;
| ^
Main.cpp:157:4: error: redefinition of 'long long int mod []'
157 | ll mod[] = {998244353, (ll)1e9 + 9};
| ^~~
Main.cpp:13:4: note: 'long long int mod [2]' previously defined here
13 | ll mod[] = {998244353, (ll)1e9 + 9};
| ^~~
Main.cpp:158:4: error: redefinition of 'long long int pw [3][500005]'
158 | ll pw[3][N], invpw[3][N];
| ^~
Main.cpp:14:4: note: 'long long int pw [3][500005]' previously declared here
14 | ll pw[3][N], invpw[3][N];
| ^~
Main.cpp:158:14: error: redefinition of 'long long int invpw [3][500005]'
158 | ll pw[3][N], invpw[3][N];
| ^~~~~
Main.cpp:14:14: note: 'long long int invpw [3][500005]' previously declared here
14 | ll pw[3][N], invpw[3][N];
| ^~~~~
Main.cpp:159:4: error: redefinition of 'long long int up [20][500005]'
159 | ll up[lg][N];
| ^~
Main.cpp:15:4: note: 'long long int up [20][500005]' previously declared here
15 | ll up[lg][N];
| ^~
Main.cpp:160:4: error: redefinition of 'long long int binpow(long long int, long long int, long long int)'
160 | ll binpow(ll n, ll p, ll mod)
| ^~~~~~
Main.cpp:16:4: note: 'long long int binpow(long long int, long long int, long long int)' previously defined here
16 | ll binpow(ll n, ll p, ll mod)
| ^~~~~~
Main.cpp:172:4: error: redefinition of 'long long int inv(long long int, long long int)'
172 | ll inv(ll n, ll mod)
| ^~~
Main.cpp:28:4: note: 'long long int inv(long long int, long long int)' previously defined here
28 | ll inv(ll n, ll mod)
| ^~~
Main.cpp:176:8: error: redefinition of 'struct SegTree'
176 | struct SegTree
| ^~~~~~~
Main.cpp:32:8: note: previous definition of 'struct SegTree'
32 | struct SegTree
| ^~~~~~~
Main.cpp:204:4: error: redefinition of 'long long int pref [2][500005]'
204 | ll pref[2][N];
| ^~~~
Main.cpp:60:4: note: 'long long int pref [2][500005]' previously declared here
60 | ll pref[2][N];
| ^~~~
Main.cpp:205:14: error: redefinition of 'std::array<long long int, 2> gethash(long long int, long long int)'
205 | array<ll, 2> gethash(ll l, ll r)
| ^~~~~~~
Main.cpp:61:14: note: 'std::array<long long int, 2> gethash(long long int, long long int)' previously defined here
61 | array<ll, 2> gethash(ll l, ll r)
| ^~~~~~~
Main.cpp:213:6: error: redefinition of 'void solve()'
213 | void solve()
| ^~~~~
Main.cpp:69:6: note: 'void solve()' previously defined here
69 | void solve()
| ^~~~~
Main.cpp: In function 'void solve()':
Main.cpp:233:26: 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]
233 | for (ll j = 0; j < e.size(); j++)
| ~~^~~~~~~~~~
Main.cpp:241:22: 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]
241 | for (ll i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
Main.cpp:244:22: 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]
244 | for (ll i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
Main.cpp:256:22: 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]
256 | for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
| ~~^~~~~~~~~~
Main.cpp:259:22: 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]
259 | for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
| ~~^~~~~~~~~~
Main.cpp:262:26: 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]
262 | for (ll i = 0; i <= s.size(); i++) up[bit][i] = up[bit - 1][up[bit - 1][i]];
| ~~^~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:279:5: error: redefinition of 'int main()'
279 | int main()
| ^~~~
Main.cpp:135:5: note: 'int main()' previously defined here
135 | int main()
| ^~~~
