Submission #859488

#	Time	Username	Problem	Language	Result	Execution time	Memory
859488		HoriaHaivas	Sum Zero (RMI20_sumzero)	C++14	Compilation error	0 ms	0 KiB

sumzero

/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct secv
{
    int l;
    int r;
    int nodeval;
};

struct cmp
{
    bool operator()(secv a, secv b)
    {
        return a.r>b.r;
    }
};

bool cmp2 (secv a, secv b)
{
    return a.l<b.l;
}

int v[100005];
long long sp[100005];
map<long long,int> last;
priority_queue<secv,vector<secv>,cmp> pq;
secv perechi[100005];
int up[17][100005];
int firstseq[100005];

secv jumpto(int node, int steps)
{
    //debug(node);
    //debug(steps);
    int i,j;
    for (j=0; j<=16; j++)
    {
        if (steps&(1<<j))
            node=up[j][node];
    }
    //debug(node);
    return perechi[node];
}

int main()
{
    //ifstream fin("stramosi.in");
    //ofstream fout("stramosi.out");
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n,q,i,j,k,cnt,best,it,mi,a,b,r,pas;
    cin >> n;
    for (j=1; j<=n; j++)
    {
        cin >> v[j];
        sp[j]=sp[j-1]+v[j];
    }
    cnt=0;
    for (j=1; j<=n; j++)
    {
        if (sp[j]==0)
        {
            cnt++;
            perechi[cnt].l=last[sp[j]]+1;
            perechi[cnt].r=j;
        }
        else
        {
            if (last[sp[j]]!=0)
            {
                cnt++;
                perechi[cnt].l=last[sp[j]]+1;
                perechi[cnt].r=j;
            }
        }
        last[sp[j]]=j;
    }
    sort(perechi+1,perechi+1+cnt,cmp2);
    for (j=1; j<=cnt; j++)
        perechi[j].nodeval=j;
    for (j=1; j<=cnt; j++)
    {
        /*
        debug(perechi[j].l);
        debug(perechi[j].r);
        cerr << "\n";
        */
        if (!pq.empty() && pq.top().r<perechi[j].l)
        {
            while (!pq.empty() && pq.top().r<perechi[j].l)
            {
                up[0][pq.top().nodeval]=perechi[j].nodeval;
                pq.pop();
            }
        }

        pq.push(perechi[j]);
        /*
        debug(pq.top().l);
        debug(pq.top().r);
        */
    }
    while (!pq.empty())
    {
        up[0][pq.top().nodeval]=0;
        pq.pop();
    }
    perechi[0].l=n+1;
    perechi[0].r=n+1;
    perechi[0].nodeval=0;
    it=cnt;
    best=0;
    for (j=n; j>=1; j--)
    {
        if (perechi[it].l==j)
        {
            if (perechi[it].r<perechi[best].r)
            {
                best=it;
            }
            it--;
        }
        firstseq[j]=best;
        /*
        debugs(j);
        debug(firstseq[j]);
        */
    }
    for (j=1; j<=16; j++)
    {
        for (i=1; i<=cnt; i++)
        {
            up[j][i]=up[j-1][up[j-1][i]];
        }
    }
    cin >> q;
    for (j=1; j<=q; j++)
    {
        cin >> a >> b;
        r=0;
        pas=(1<<16);
        while (pas)
        {
            if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
                r+=pas;
            pas=pas/2;
        }
        cout << r+1 << "\n";
    }
    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'secv jumpto(int, int)':
sumzero.cpp:44:9: warning: unused variable 'i' [-Wunused-variable]
   44 |     int i,j;
      |         ^
sumzero.cpp: In function 'int main()':
sumzero.cpp:154:56: error: no match for 'operator!=' (operand types are 'secv' and 'int')
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
      |                                     |                    |
      |                                     secv                 int
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1064:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1064 |     operator!=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1064:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1144:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1144 |     operator!=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1144:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1237:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1237 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1237:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1311:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1311 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1311:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1405:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1405 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1405:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1479:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1479 |     operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1479:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:1579:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1579 |     operator!=(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1579:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/regex.h:2126:5: note: candidate: 'template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator!=(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)'
 2126 |     operator!=(const match_results<_Bi_iter, _Alloc>& __m1,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:2126:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/postypes.h:227:5: note: candidate: 'template<class _StateT> bool std::operator!=(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
  227 |     operator!=(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/postypes.h:227:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::fpos<_StateT>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/stl_pair.h:496:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator!=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  496 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:496:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::pair<_T1, _T2>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/stl_iterator.h:372:5: note: candidate: 'template<class _Iterator> bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  372 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:372:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::reverse_iterator<_Iterator>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/stl_iterator.h:410:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  410 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:410:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::reverse_iterator<_Iterator>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/stl_iterator.h:1444:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1444 |     operator!=(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1444:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::move_iterator<_IteratorL>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/stl_iterator.h:1501:5: note: candidate: 'template<class _Iterator> bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1501 |     operator!=(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1501:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::move_iterator<_IteratorL>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/allocator.h:213:5: note: candidate: 'template<class _T1, class _T2> bool std::operator!=(const std::allocator<_CharT>&, const std::allocator<_T2>&)'
  213 |     operator!=(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/10/bits/allocator.h:213:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::allocator<_CharT>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/basic_string.h:6229:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
 6229 |     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6229:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   'secv' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/basic_string.h:6242:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
 6242 |     operator!=(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6242:5: note:   template argument deduction/substitution failed:
sumzero.cpp:154:58: note:   mismatched types 'const _CharT*' and 'secv'
  154 |             if (r+pas<=cnt && jumpto(firstseq[a],r+pas)!=0 && jumpto(firstseq[a],r+pas).r<=b)
      |                                                          ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sumzero.cpp:5:
/usr/include/c++/10/bits/basic_string.h:6254:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)'
 6254 |     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_st