oj.uz

Submission #1001885

# Submission time Handle Problem Language Result Execution time Memory
1001885 2024-06-19T08:18:30 Z Nelt Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 104780 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 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("");
  	string s;
    cin >> s;
    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));
    }
    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;
        if (rig[l] >= r) cout << "1\n";
        else
        {
            ll ans = 0;
            for (ll bit = lg - 1; bit >= 0; bit--) if (rig[up[bit][l]] < r and up[bit][l] < r) ans += 1 << bit, l = up[bit][l];
            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

Main.cpp: In function 'void solve()':
Main.cpp:75:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
   75 |         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));
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:78: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]
   78 |     for (ll i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
Main.cpp:85: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]
   85 |     for (ll i = 0; i < s.size(); i++)
      |                    ~~^~~~~~~~~~
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++) st.set(i, rig[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++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
      |                    ~~^~~~~~~~~~
Main.cpp:103: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]
  103 |         for (ll i = 0; i <= s.size(); i++) up[bit][i] = up[bit - 1][up[bit - 1][i]];
      |                        ~~^~~~~~~~~~~
Main.cpp:80:10: warning: variable 'gethash' set but not used [-Wunused-but-set-variable]
   80 |     auto gethash = [&](ll l, ll r)
      |          ^~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8276 KB Output is correct
2 Correct 167 ms 44632 KB Output is correct
3 Correct 191 ms 54868 KB Output is correct
4 Correct 230 ms 59556 KB Output is correct
5 Correct 217 ms 81500 KB Output is correct
6 Correct 233 ms 71248 KB Output is correct
7 Correct 135 ms 25032 KB Output is correct
8 Correct 237 ms 81744 KB Output is correct
9 Correct 241 ms 104780 KB Output is correct
10 Correct 135 ms 27216 KB Output is correct
11 Correct 93 ms 12352 KB Output is correct
12 Correct 88 ms 11800 KB Output is correct
13 Correct 89 ms 12112 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1990 ms 90564 KB Output is correct
2 Execution timed out 2048 ms 59736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8276 KB Output is correct
2 Correct 167 ms 44632 KB Output is correct
3 Correct 191 ms 54868 KB Output is correct
4 Correct 230 ms 59556 KB Output is correct
5 Correct 217 ms 81500 KB Output is correct
6 Correct 233 ms 71248 KB Output is correct
7 Correct 135 ms 25032 KB Output is correct
8 Correct 237 ms 81744 KB Output is correct
9 Correct 241 ms 104780 KB Output is correct
10 Correct 135 ms 27216 KB Output is correct
11 Correct 93 ms 12352 KB Output is correct
12 Correct 88 ms 11800 KB Output is correct
13 Correct 89 ms 12112 KB Output is correct
14 Correct 1990 ms 90564 KB Output is correct
15 Execution timed out 2048 ms 59736 KB Time limit exceeded
16 Halted 0 ms 0 KB -