Submission #1275946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275946		domi	Election (BOI18_election)	C++20	Compilation error	0 ms	0 KiB

election

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

//using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 5e5;

using namespace std;

vector<pii>qu[NMAX + 5];
vector<int>stk;
char ch;
int a[NMAX + 5], ans[NMAX + 5], n, q;

///cate numere din stk sunt <= r
inline int cate(int r){
    if (stk.empty()) return 0;
    return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
}

struct Node{
    int sum;
    int min_suf;

    Node () : sum(0), min_suf(0) {}

    Node (int x) : sum(x), min_suf(min(0LL, x)) {}

    static Node merge(const Node& left, const Node& right){
        Node aux;
        aux.sum = left.sum + right.sum;
        aux.min_suf = min(right.min_suf, right.sum + left.min_suf);
        return aux;
    }

};

struct ST{

    Node aint[4 * NMAX + 5];

    void build(int nod = 1, int st = 1, int dr = n){
        if (st == dr){
            aint[nod] = Node(a[st]);
            return;
        }

        int m = (st + dr) >> 1;
        build(2 * nod, st, m);
        build(2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    void update(int pos, int val, int nod = 1, int st = 1, int dr = n){
        if (st == dr){
            aint[nod] = Node(val);
            return;
        }

        int m = (st + dr) >> 1;
        if (pos <= m)
            update(pos, val, 2 * nod, st, m);
        else
            update(pos, val, 2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    Node query(int l, int r, int nod = 1, int st = 1, int dr = n){
        if (st > r || dr < l) return Node();
        if (l <= st && dr <= r) return aint[nod];

        int m = (st + dr) >> 1;
        return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
     }


}aint;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

    for (int i = 1; i <= n; ++i){
        cin >> ch;
        a[i] = (ch == 'C' ? 1 : -1);
    }

    cin >> q;
    for (int i = 1, l, r; i <= q; ++i){
        cin >> l >> r;
        qu[l].push_back({r, i});
    }

    aint.build();
    for (int i = n; i >= 1; ++i){

        if (a[i] == 1){
            if (!st.empty()){
                aint.update(st.back(), -1);
                st.pop_back();
            }
        }

        if (a[i] == -1){
            aint.update(i, 0);
            stk.push_back(i);
        }

        for (auto &[r, idx] : qu[i])
            ans[idx] = cate(r) - aint.query(i, r).min_suf;
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'long long int cate(long long int)':
election.cpp:30:53: error: no match for 'operator-' (operand types are 'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' and 'std::vector<long long int>::iterator')
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~~~~~
      |                       |                                        |
      |                       |                                        std::vector<long long int>::iterator
      |                       std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from election.cpp:1:
/usr/include/c++/13/bits/stl_iterator.h:370:7: note: candidate: 'constexpr std::reverse_iterator<_Iterator> std::reverse_iterator<_Iterator>::operator-(difference_type) const [with _Iterator = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; difference_type = long int]'
  370 |       operator-(difference_type __n) const
      |       ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:370:33: note:   no known conversion for argument 1 from 'std::vector<long long int>::iterator' to 'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >::difference_type' {aka 'long int'}
  370 |       operator-(difference_type __n) const
      |                 ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_iterator.h:625:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_IteratorL>&, const reverse_iterator<_IteratorR>&)'
  625 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:625:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::vector<long long int>::iterator' is not derived from 'const std::reverse_iterator<_IteratorR>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1800 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::move_iterator<_IteratorL>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
In file included from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/complex:365:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&, const complex<_Tp>&)'
  365 |     operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:365:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::complex<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/complex:374:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&, const _Tp&)'
  374 |     operator-(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:374:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::complex<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/complex:383:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const _Tp&, const complex<_Tp>&)'
  383 |     operator-(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/complex:383:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::vector<long long int>::iterator' is not derived from 'const std::complex<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/complex:460:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator-(const complex<_Tp>&)'
  460 |     operator-(const complex<_Tp>& __x)
      |     ^~~~~~~~
/usr/include/c++/13/complex:460:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::complex<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
In file included from /usr/include/c++/13/valarray:605,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const typename _Dom::value_type&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::vector<long long int>::iterator' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const valarray<typename _Dom::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const valarray<typename _Dom::value_type>&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::vector<long long int>::iterator' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/valarray:1197:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const valarray<_Tp>&, const valarray<_Tp>&)'
 1197 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1197:1: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::valarray<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/valarray:1197:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const valarray<_Tp>&, const typename valarray<_Tp>::value_type&)'
 1197 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1197:1: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const std::valarray<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/valarray:1197:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const typename valarray<_Tp>::value_type&, const valarray<_Tp>&)'
 1197 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1197:1: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::vector<long long int>::iterator' is not derived from 'const std::valarray<_Tp>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/stl_iterator.h:1321:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> constexpr decltype ((__lhs.base() - __rhs.base())) __gnu_cxx::operator-(const __normal_iterator<_IteratorL, _Container>&, const __normal_iterator<_IteratorR, _Container>&)'
 1321 |     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1321:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
/usr/include/c++/13/bits/stl_iterator.h:1334:5: note: candidate: 'template<class _Iterator, class _Container> constexpr typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type __gnu_cxx::operator-(const __normal_iterator<_Iterator, _Container>&, const __normal_iterator<_Iterator, _Container>&)'
 1334 |     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1334:5: note:   template argument deduction/substitution failed:
election.cpp:30:65: note:   'std::reverse_iterator<__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> > >' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   30 |     return upper_bound(stk.rbegin(), stk.rend(), r) - stk.begin();
      |                                                                 ^
election.cpp: In function 'int main()':
election.cpp:110:18: error: 'st' was not declared in this scope; did you mean 'stk'?
  110 |             if (!st.empty()){
      |                  ^~
      |                  stk