Submission #1001586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001586		vjudge1	Dabbeh (INOI20_dabbeh)	C++17	0 / 100	1088 ms	78264 KiB

Main

#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<ll> hs;
    hs.insert(0);
    for (ll i = 0; i < n; i++)
    {
        ll cur = 0;
        for (ll j = 0; j < t[i].size(); j++) cur = (cur + (t[i][j] - 'a' + 1) * pw[j]) % mod, hs.insert(cur);
    }
    string s;
    cin >> s;
    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;
        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());
    for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
    st.build();
    for (ll i = 0; i < s.size(); i++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i] - 1).second;
    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;
        cout << "a\n";
            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;
            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 (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:73: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]
   73 |         for (ll j = 0; j < t[i].size(); j++) cur = (cur + (t[i][j] - 'a' + 1) * pw[j]) % mod, hs.insert(cur);
      |                        ~~^~~~~~~~~~~~~
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:96: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]
   96 |     for (ll i = 0; i < s.size(); i++) st.set(i, rig[i]);
      |                    ~~^~~~~~~~~~
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++) up[0][i] = rig[i] == i ? i : st.query(i, rig[i] - 1).second;
      |                    ~~^~~~~~~~~~
Main.cpp:100: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]
  100 |         for (ll i = 0; i < s.size(); i++) up[bit][i] = up[bit - 1][up[bit - 1][i]];
      |                        ~~^~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 50