Submission #1002064

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1002064	2024-06-19T09:37:03 Z	Nelt	Dabbeh (INOI20_dabbeh)	C++17	Compilation error	0 ms	0 KB

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 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<ll, 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: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:93:26: error: no matching function for call to 'std::set<std::array<int, 2> >::insert(std::array<long long int, 2>&)'
   93 |             hs.insert(cur);
      |                          ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_set.h:509:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::array<int, 2>]'
  509 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:509:32: note:   no known conversion for argument 1 from 'std::array<long long int, 2>' to 'const value_type&' {aka 'const std::array<int, 2>&'}
  509 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:518:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::array<int, 2>]'
  518 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:518:27: note:   no known conversion for argument 1 from 'std::array<long long int, 2>' to 'std::set<std::array<int, 2> >::value_type&&' {aka 'std::array<int, 2>&&'}
  518 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:546:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::array<int, 2>]'
  546 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:546:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:551:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::array<int, 2>]'
  551 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:551:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:566:2: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >]'
  566 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_set.h:566:2: note:   template argument deduction/substitution failed:
Main.cpp:93:26: note:   candidate expects 2 arguments, 1 provided
   93 |             hs.insert(cur);
      |                          ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_set.h:578:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >]'
  578 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:578:43: note:   no known conversion for argument 1 from 'std::array<long long int, 2>' to 'std::initializer_list<std::array<int, 2> >'
  578 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:598:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::insert_return_type std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >; std::set<_Key, _Compare, _Alloc>::insert_return_type = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::insert_return_type; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::node_type]'
  598 |       insert(node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:598:26: note:   no known conversion for argument 1 from 'std::array<long long int, 2>' to 'std::set<std::array<int, 2> >::node_type&&' {aka 'std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::node_type&&'}
  598 |       insert(node_type&& __nh)
      |              ~~~~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::array<int, 2>; _Compare = std::less<std::array<int, 2> >; _Alloc = std::allocator<std::array<int, 2> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::array<int, 2>, std::array<int, 2>, std::_Identity<std::array<int, 2> >, std::less<std::array<int, 2> >, std::allocator<std::array<int, 2> > >::node_type]'
  603 |       insert(const_iterator __hint, node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note:   candidate expects 2 arguments, 1 provided
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]];
      |                        ~~^~~~~~~~~~~