oj.uz

Submission #1002059

# Submission time Handle Problem Language Result Execution time Memory
1002059 2024-06-19T09:34:00 Z Nelt Dabbeh (INOI20_dabbeh) C++17
25 / 100
 1437 ms 65300 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll int
#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};
long long 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 = 1ll * ans * (p & 1 ? n : 1) % mod;
        p >>= 1;
        n = 1ll * 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] = 1ll * (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] = 1ll * pw[x][i - 1] * p % mod[x];
        for (ll i = 1; i < N; i++) invpw[x][i] = 1ll * 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] + 1ll * (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]) + 1ll * (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, mid;
        rig[i] = i;
        while (l <= r)
        {
            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: In function 'void solve()':
Main.cpp:89:26: warning: comparison of integer expressions of different signedness: '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: '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: '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: '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: '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: '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]];
      |                        ~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16472 KB Output is correct
2 Correct 216 ms 35152 KB Output is correct
3 Correct 158 ms 30092 KB Output is correct
4 Correct 189 ms 35056 KB Output is correct
5 Correct 185 ms 33104 KB Output is correct
6 Correct 239 ms 37972 KB Output is correct
7 Correct 262 ms 40020 KB Output is correct
8 Correct 237 ms 39104 KB Output is correct
9 Correct 196 ms 36616 KB Output is correct
10 Correct 92 ms 21588 KB Output is correct
11 Correct 194 ms 37664 KB Output is correct
12 Correct 97 ms 26692 KB Output is correct
13 Correct 153 ms 32624 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 56184 KB Output is correct
2 Correct 1321 ms 62588 KB Output is correct
3 Correct 1134 ms 57544 KB Output is correct
4 Correct 935 ms 52412 KB Output is correct
5 Correct 924 ms 52256 KB Output is correct
6 Correct 1365 ms 62700 KB Output is correct
7 Incorrect 1437 ms 65300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16472 KB Output is correct
2 Correct 216 ms 35152 KB Output is correct
3 Correct 158 ms 30092 KB Output is correct
4 Correct 189 ms 35056 KB Output is correct
5 Correct 185 ms 33104 KB Output is correct
6 Correct 239 ms 37972 KB Output is correct
7 Correct 262 ms 40020 KB Output is correct
8 Correct 237 ms 39104 KB Output is correct
9 Correct 196 ms 36616 KB Output is correct
10 Correct 92 ms 21588 KB Output is correct
11 Correct 194 ms 37664 KB Output is correct
12 Correct 97 ms 26692 KB Output is correct
13 Correct 153 ms 32624 KB Output is correct
14 Correct 1093 ms 56184 KB Output is correct
15 Correct 1321 ms 62588 KB Output is correct
16 Correct 1134 ms 57544 KB Output is correct
17 Correct 935 ms 52412 KB Output is correct
18 Correct 924 ms 52256 KB Output is correct
19 Correct 1365 ms 62700 KB Output is correct
20 Incorrect 1437 ms 65300 KB Output isn't correct
21 Halted 0 ms 0 KB -