oj.uz

Submission #1002015

# Submission time Handle Problem Language Result Execution time Memory
1002015 2024-06-19T09:15:20 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 98860 KB 
#pragma GCC optimize("O3,unroll-loops")
#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 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[2][N];
array<ll, 2> gethash(ll l, ll r)
{
    if (l > r) return array<ll, 2>{0, 0};
    array<ll, 2> ans = {0, 0};
    for (ll i = 0; i < 2; 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 < 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] = 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, 2>> hs;
    hs.insert({0, 0});
  	string s;
    cin >> s;
    for (string e : t)
    {
        array<ll, 2> cur = {0, 0};
        for (ll j = 0; j < e.size(); j++)
        { 
            for (ll x = 0; x < 2; x++)
            cur[x] = (cur[x] + (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]) + (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;
        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 12 ms 16216 KB Output is correct
2 Correct 188 ms 43244 KB Output is correct
3 Correct 156 ms 36692 KB Output is correct
4 Correct 201 ms 43344 KB Output is correct
5 Correct 196 ms 40784 KB Output is correct
6 Correct 227 ms 47188 KB Output is correct
7 Correct 334 ms 50112 KB Output is correct
8 Correct 256 ms 48872 KB Output is correct
9 Correct 254 ms 45652 KB Output is correct
10 Correct 92 ms 25552 KB Output is correct
11 Correct 245 ms 47168 KB Output is correct
12 Correct 117 ms 32280 KB Output is correct
13 Correct 163 ms 40400 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1339 ms 90900 KB Output is correct
2 Correct 1560 ms 98764 KB Output is correct
3 Correct 1330 ms 92120 KB Output is correct
4 Correct 1018 ms 85496 KB Output is correct
5 Correct 1059 ms 85072 KB Output is correct
6 Correct 1993 ms 98860 KB Output is correct
7 Execution timed out 2084 ms 45720 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16216 KB Output is correct
2 Correct 188 ms 43244 KB Output is correct
3 Correct 156 ms 36692 KB Output is correct
4 Correct 201 ms 43344 KB Output is correct
5 Correct 196 ms 40784 KB Output is correct
6 Correct 227 ms 47188 KB Output is correct
7 Correct 334 ms 50112 KB Output is correct
8 Correct 256 ms 48872 KB Output is correct
9 Correct 254 ms 45652 KB Output is correct
10 Correct 92 ms 25552 KB Output is correct
11 Correct 245 ms 47168 KB Output is correct
12 Correct 117 ms 32280 KB Output is correct
13 Correct 163 ms 40400 KB Output is correct
14 Correct 1339 ms 90900 KB Output is correct
15 Correct 1560 ms 98764 KB Output is correct
16 Correct 1330 ms 92120 KB Output is correct
17 Correct 1018 ms 85496 KB Output is correct
18 Correct 1059 ms 85072 KB Output is correct
19 Correct 1993 ms 98860 KB Output is correct
20 Execution timed out 2084 ms 45720 KB Time limit exceeded
21 Halted 0 ms 0 KB -