Submission #1001978

#TimeUsernameProblemLanguageResultExecution timeMemory
1001978vjudge1Dabbeh (INOI20_dabbeh)C++17
25 / 100
2048 ms101128 KiB
#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)1e9 + 7}; 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[3][N]; array<ll, 3> gethash(ll l, ll r) { if (l > r) return array<ll, 3>{0, 0, 0}; array<ll, 3> ans = {0, 0, 0}; for (ll i = 0; i < 3; 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 < 3; x++) pw[x][0] = 1; for (ll x = 0; x < 3; x++) { for (ll i = 1; i < N; i++) pw[x][i] = pw[x][i - 1] * p % mod[x]; for (ll i = 0; i < N; i++) invpw[x][i] = inv(pw[x][i], mod[x]); } set<array<ll, 3>> hs; hs.insert({0, 0, 0}); string s; cin >> s; for (string e : t) { array<ll, 3> cur = {0, 0, 0}; for (ll j = 0; j < e.size(); j++) { for (ll x = 0; x < 3; x++) cur[x] = (cur[x] + (e[j] - 'a' + 1) * pw[x][j]) % mod[x]; hs.insert(cur); } } for (ll x = 0; x < 3; 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; 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"; }

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:88: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]
   88 |         for (ll j = 0; j < e.size(); j++)
      |                        ~~^~~~~~~~~~
Main.cpp:96: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]
   96 |     for (ll i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:99: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]
   99 |     for (ll i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:111: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]
  111 |     for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
      |                    ~~^~~~~~~~~~
Main.cpp:114: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]
  114 |     for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
      |                    ~~^~~~~~~~~~
Main.cpp:117: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]
  117 |         for (ll i = 0; i <= s.size(); i++) up[bit][i] = up[bit - 1][up[bit - 1][i]];
      |                        ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...