oj.uz

Submission #1001996

# Submission time Handle Problem Language Result Execution time Memory
1001996 2024-06-19T09:03:01 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 101072 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 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] = invpw[x][0] = 1;
    for (ll x = 0; x < 3; x++)
    {
        ll invp = inv(p, mod[x]);
        for (ll i = 1; i < N; i++) pw[x][i] = pw[x][i - 1] * p % mod[x];
        for (ll i = 1; i < N; i++) invpw[x][i] = invpw[x][i - 1] * invp % 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;
        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:89: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]
   89 |         for (ll j = 0; j < e.size(); j++)
      |                        ~~^~~~~~~~~~
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++)
      |                    ~~^~~~~~~~~~
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++)
      |                    ~~^~~~~~~~~~
Main.cpp:112: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]
  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: 'long long 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: 'long long 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 21 ms 23892 KB Output is correct
2 Correct 207 ms 51052 KB Output is correct
3 Correct 183 ms 44564 KB Output is correct
4 Correct 261 ms 51064 KB Output is correct
5 Correct 207 ms 48716 KB Output is correct
6 Correct 278 ms 55120 KB Output is correct
7 Correct 359 ms 57936 KB Output is correct
8 Correct 307 ms 56744 KB Output is correct
9 Correct 234 ms 53392 KB Output is correct
10 Correct 117 ms 33360 KB Output is correct
11 Correct 295 ms 54936 KB Output is correct
12 Correct 149 ms 40212 KB Output is correct
13 Correct 221 ms 48180 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 101072 KB Output is correct
2 Execution timed out 2080 ms 52288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23892 KB Output is correct
2 Correct 207 ms 51052 KB Output is correct
3 Correct 183 ms 44564 KB Output is correct
4 Correct 261 ms 51064 KB Output is correct
5 Correct 207 ms 48716 KB Output is correct
6 Correct 278 ms 55120 KB Output is correct
7 Correct 359 ms 57936 KB Output is correct
8 Correct 307 ms 56744 KB Output is correct
9 Correct 234 ms 53392 KB Output is correct
10 Correct 117 ms 33360 KB Output is correct
11 Correct 295 ms 54936 KB Output is correct
12 Correct 149 ms 40212 KB Output is correct
13 Correct 221 ms 48180 KB Output is correct
14 Correct 1637 ms 101072 KB Output is correct
15 Execution timed out 2080 ms 52288 KB Time limit exceeded
16 Halted 0 ms 0 KB -