oj.uz

Submission #1001878

# Submission time Handle Problem Language Result Execution time Memory
1001878 2024-06-19T08:14:56 Z Nelt Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 104784 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) 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 64 ms 8272 KB Output is correct
2 Correct 178 ms 43856 KB Output is correct
3 Correct 212 ms 54768 KB Output is correct
4 Correct 268 ms 59600 KB Output is correct
5 Correct 231 ms 81488 KB Output is correct
6 Correct 256 ms 71252 KB Output is correct
7 Correct 169 ms 25168 KB Output is correct
8 Correct 287 ms 82000 KB Output is correct
9 Correct 265 ms 104784 KB Output is correct
10 Correct 136 ms 27212 KB Output is correct
11 Correct 95 ms 12348 KB Output is correct
12 Correct 95 ms 11744 KB Output is correct
13 Correct 89 ms 11936 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8272 KB Output is correct
2 Correct 178 ms 43856 KB Output is correct
3 Correct 212 ms 54768 KB Output is correct
4 Correct 268 ms 59600 KB Output is correct
5 Correct 231 ms 81488 KB Output is correct
6 Correct 256 ms 71252 KB Output is correct
7 Correct 169 ms 25168 KB Output is correct
8 Correct 287 ms 82000 KB Output is correct
9 Correct 265 ms 104784 KB Output is correct
10 Correct 136 ms 27212 KB Output is correct
11 Correct 95 ms 12348 KB Output is correct
12 Correct 95 ms 11744 KB Output is correct
13 Correct 89 ms 11936 KB Output is correct
14 Execution timed out 2041 ms 33972 KB Time limit exceeded
15 Halted 0 ms 0 KB -