oj.uz

Submission #1002077

# Submission time Handle Problem Language Result Execution time Memory
1002077 2024-06-19T09:43:08 Z Nelt Dabbeh (INOI20_dabbeh) C++17
50 / 100
 2000 ms 108224 KB 
#pragma GCC optimize("O3")
#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};
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<int, 2> gethash(ll l, ll r)
{
    if (l > r) return array<int, 2>{0, 0};
    array<int, 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<int, 2>> hs;
    hs.insert({0, 0});
  	string s;
    cin >> s;
    for (string e : t)
    {
        array<int, 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:90: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]
   90 |         for (ll j = 0; j < e.size(); j++)
      |                        ~~^~~~~~~~~~
Main.cpp:98: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]
   98 |     for (ll i = 0; i < s.size(); 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++)
      |                    ~~^~~~~~~~~~
Main.cpp:113: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]
  113 |     for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
      |                    ~~^~~~~~~~~~
Main.cpp:116: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]
  116 |     for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i]).second;
      |                    ~~^~~~~~~~~~
Main.cpp:119: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]
  119 |         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 16216 KB Output is correct
2 Correct 210 ms 37220 KB Output is correct
3 Correct 156 ms 32592 KB Output is correct
4 Correct 218 ms 37456 KB Output is correct
5 Correct 182 ms 35668 KB Output is correct
6 Correct 237 ms 40532 KB Output is correct
7 Correct 309 ms 42836 KB Output is correct
8 Correct 244 ms 41860 KB Output is correct
9 Correct 221 ms 39248 KB Output is correct
10 Correct 89 ms 23928 KB Output is correct
11 Correct 220 ms 40252 KB Output is correct
12 Correct 106 ms 29072 KB Output is correct
13 Correct 152 ms 35232 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 88336 KB Output is correct
2 Correct 1370 ms 94408 KB Output is correct
3 Correct 1173 ms 89220 KB Output is correct
4 Correct 1044 ms 84104 KB Output is correct
5 Correct 963 ms 83932 KB Output is correct
6 Correct 1397 ms 94400 KB Output is correct
7 Correct 1543 ms 96992 KB Output is correct
8 Correct 1332 ms 91952 KB Output is correct
9 Correct 1453 ms 95128 KB Output is correct
10 Correct 1722 ms 98724 KB Output is correct
11 Correct 1282 ms 89524 KB Output is correct
12 Correct 1216 ms 87900 KB Output is correct
13 Correct 1622 ms 100648 KB Output is correct
14 Correct 1585 ms 98132 KB Output is correct
15 Correct 747 ms 82160 KB Output is correct
16 Correct 1156 ms 100736 KB Output is correct
17 Correct 725 ms 86404 KB Output is correct
18 Correct 668 ms 86204 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16216 KB Output is correct
2 Correct 210 ms 37220 KB Output is correct
3 Correct 156 ms 32592 KB Output is correct
4 Correct 218 ms 37456 KB Output is correct
5 Correct 182 ms 35668 KB Output is correct
6 Correct 237 ms 40532 KB Output is correct
7 Correct 309 ms 42836 KB Output is correct
8 Correct 244 ms 41860 KB Output is correct
9 Correct 221 ms 39248 KB Output is correct
10 Correct 89 ms 23928 KB Output is correct
11 Correct 220 ms 40252 KB Output is correct
12 Correct 106 ms 29072 KB Output is correct
13 Correct 152 ms 35232 KB Output is correct
14 Correct 1164 ms 88336 KB Output is correct
15 Correct 1370 ms 94408 KB Output is correct
16 Correct 1173 ms 89220 KB Output is correct
17 Correct 1044 ms 84104 KB Output is correct
18 Correct 963 ms 83932 KB Output is correct
19 Correct 1397 ms 94400 KB Output is correct
20 Correct 1543 ms 96992 KB Output is correct
21 Correct 1332 ms 91952 KB Output is correct
22 Correct 1453 ms 95128 KB Output is correct
23 Correct 1722 ms 98724 KB Output is correct
24 Correct 1282 ms 89524 KB Output is correct
25 Correct 1216 ms 87900 KB Output is correct
26 Correct 1622 ms 100648 KB Output is correct
27 Correct 1585 ms 98132 KB Output is correct
28 Correct 747 ms 82160 KB Output is correct
29 Correct 1156 ms 100736 KB Output is correct
30 Correct 725 ms 86404 KB Output is correct
31 Correct 668 ms 86204 KB Output is correct
32 Correct 719 ms 65300 KB Output is correct
33 Correct 1016 ms 75532 KB Output is correct
34 Correct 1213 ms 80884 KB Output is correct
35 Correct 1108 ms 78328 KB Output is correct
36 Correct 1309 ms 84024 KB Output is correct
37 Correct 729 ms 65044 KB Output is correct
38 Correct 1898 ms 105120 KB Output is correct
39 Correct 1533 ms 94484 KB Output is correct
40 Correct 1984 ms 108224 KB Output is correct
41 Execution timed out 2028 ms 107928 KB Time limit exceeded
42 Halted 0 ms 0 KB -