oj.uz

Submission #1001890

# Submission time Handle Problem Language Result Execution time Memory
1001890 2024-06-19T08:19:53 Z Nelt Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 104424 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());
    rig[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) 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:101: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]
  101 |     for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
      |                    ~~^~~~~~~~~~
Main.cpp:104: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]
  104 |         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 67 ms 8272 KB Output is correct
2 Correct 215 ms 44624 KB Output is correct
3 Correct 206 ms 54796 KB Output is correct
4 Correct 241 ms 59220 KB Output is correct
5 Correct 260 ms 81236 KB Output is correct
6 Correct 265 ms 70952 KB Output is correct
7 Correct 146 ms 24644 KB Output is correct
8 Correct 310 ms 81232 KB Output is correct
9 Correct 256 ms 104424 KB Output is correct
10 Correct 152 ms 27180 KB Output is correct
11 Correct 98 ms 11832 KB Output is correct
12 Correct 99 ms 11800 KB Output is correct
13 Correct 99 ms 11816 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 34016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8272 KB Output is correct
2 Correct 215 ms 44624 KB Output is correct
3 Correct 206 ms 54796 KB Output is correct
4 Correct 241 ms 59220 KB Output is correct
5 Correct 260 ms 81236 KB Output is correct
6 Correct 265 ms 70952 KB Output is correct
7 Correct 146 ms 24644 KB Output is correct
8 Correct 310 ms 81232 KB Output is correct
9 Correct 256 ms 104424 KB Output is correct
10 Correct 152 ms 27180 KB Output is correct
11 Correct 98 ms 11832 KB Output is correct
12 Correct 99 ms 11800 KB Output is correct
13 Correct 99 ms 11816 KB Output is correct
14 Execution timed out 2059 ms 34016 KB Time limit exceeded
15 Halted 0 ms 0 KB -