oj.uz

Submission #1002013

# Submission time Handle Problem Language Result Execution time Memory
1002013 2024-06-19T09:13:25 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 2000 ms 99040 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 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: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 13 ms 16216 KB Output is correct
2 Correct 212 ms 43140 KB Output is correct
3 Correct 149 ms 36760 KB Output is correct
4 Correct 217 ms 43224 KB Output is correct
5 Correct 182 ms 40936 KB Output is correct
6 Correct 256 ms 47184 KB Output is correct
7 Correct 281 ms 50156 KB Output is correct
8 Correct 254 ms 48980 KB Output is correct
9 Correct 256 ms 45792 KB Output is correct
10 Correct 91 ms 25556 KB Output is correct
11 Correct 205 ms 47172 KB Output is correct
12 Correct 115 ms 32280 KB Output is correct
13 Correct 164 ms 40460 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 90900 KB Output is correct
2 Correct 1729 ms 98724 KB Output is correct
3 Correct 1340 ms 92172 KB Output is correct
4 Correct 1082 ms 85464 KB Output is correct
5 Correct 1050 ms 85108 KB Output is correct
6 Correct 1566 ms 99040 KB Output is correct
7 Execution timed out 2044 ms 45712 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16216 KB Output is correct
2 Correct 212 ms 43140 KB Output is correct
3 Correct 149 ms 36760 KB Output is correct
4 Correct 217 ms 43224 KB Output is correct
5 Correct 182 ms 40936 KB Output is correct
6 Correct 256 ms 47184 KB Output is correct
7 Correct 281 ms 50156 KB Output is correct
8 Correct 254 ms 48980 KB Output is correct
9 Correct 256 ms 45792 KB Output is correct
10 Correct 91 ms 25556 KB Output is correct
11 Correct 205 ms 47172 KB Output is correct
12 Correct 115 ms 32280 KB Output is correct
13 Correct 164 ms 40460 KB Output is correct
14 Correct 1209 ms 90900 KB Output is correct
15 Correct 1729 ms 98724 KB Output is correct
16 Correct 1340 ms 92172 KB Output is correct
17 Correct 1082 ms 85464 KB Output is correct
18 Correct 1050 ms 85108 KB Output is correct
19 Correct 1566 ms 99040 KB Output is correct
20 Execution timed out 2044 ms 45712 KB Time limit exceeded
21 Halted 0 ms 0 KB -