Submission #884121

# Submission time Handle Problem Language Result Execution time Memory
884121 2023-12-06T16:01:23 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
Compilation error
0 ms 0 KB
#include "bubblesort2.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int , int> , null_type, less<pair<int , int>>, rb_tree_tag, tree_order_statistics_node_update> orderedSet;

map<int, priority_queue<int> > q;

struct AINT {
    vector<pair<int , int> > aint;
    vector<int> lazy;
    int n, offset;
    
    AINT (int _n)
    {
        n = _n;
        offset = 1;
        while (offset < n) offset <<= 1;
        aint.resize(2*offset, 0);
        lazy.resize(2*offset, 0);
        
    }
    
    void updatePos (int pos, int val)
    {
        int nod = offset + pos - 1;
        for (int i = nod; i > 0; i /= 2)
        {
            aint[nod] = val;
            aint[nod/2] = merge(aint[nod] , aint[nod^1]);
        }
    }
    
    void updateInt (int l, int r, int val)
    {
        upd(1, 1, offset, l, r, val);
    }
    
    void upd (int nod, int l, int r, int ul, int ur, int val)
    {
        if (ul <= l && r <= ur) {
            lazy[nod] += val;
        }
        else if (l > ur || r < ul) return;
        int mid = (l+r)/2;
        upd(2*nod, l, mid, ul, ur, val);
        upd(2*nod+1, mid+1, r, ul, ur, val);
        aint[nod] = merge(aint[2*nod] , aint[2*nod+1]);
    }
    
    
    
private:
    void pushLazy (int nod)
    {
        
        if (nod >= offset)
        {
            aint[nod].second += lazy[nod];
            lazy[nod] = 0;
        }
        else {
            aint[nod].second += lazy[nod];
            lazy[2*nod] += lazy[nod];
            lazy[2*nod+1] += lazy[nod];
            lazy[nod] = 0;
        }
        
    }
    int mergeAint (pair<int , int> a1, int l1, pair<int , int> a2, int l2)
    {
        if (a1.first - a1.second > a2.first - a2.second){
            return a1;
        }
        else return a2;
    }
    int mergeLazy (int l1, int l2)
    {
        return l1+l2;
    }
};

map<int , int> norm;
map<int , bool> used;

std::vector<int> countScans(std::vector<int> a,std::vector<int> X,std::vector<int> V){
	int Q=X.size();
	int n = a.size();
	std::vector<int> answer(Q);
    AINT aint(vals.size());
    vector<int> vals;
    for (int i = 0; i < n; i++)
    {
        if (!used[a[i]]) {
            vals.push_back(a[i]);
            used[a[i]] = 1;
        }
        q[a[i]].push(i);
        
    }
    for (int i = 0; i < q; i++)
    {
        if(!used[V[i]])
        {
            used[V[i]] = 1;
            vals.push_back(V[i]);
        }
    }
    sort(vals.begin() , vals.end())
    for (int i = 0; i < vals.size(); i++)
    {
        norm[vals[i]] = i+1;
    }
    
    for ()
    
    for (int i = 0; i < Q; i++)
    {
        aint.updateInt ()
    }

	return answer;
}

Compilation message

bubblesort2.cpp: In constructor 'AINT::AINT(int)':
bubblesort2.cpp:23:32: error: no matching function for call to 'std::vector<std::pair<int, int> >::resize(int, int)'
   23 |         aint.resize(2*offset, 0);
      |                                ^
In file included from /usr/include/c++/10/vector:67,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:937:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
  937 |       resize(size_type __new_size)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:937:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:957:7: note: candidate: 'void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
  957 |       resize(size_type __new_size, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:957:54: note:   no known conversion for argument 2 from 'int' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  957 |       resize(size_type __new_size, const value_type& __x)
      |                                    ~~~~~~~~~~~~~~~~~~^~~
bubblesort2.cpp: In member function 'void AINT::updatePos(int, int)':
bubblesort2.cpp:33:25: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} and 'int')
   33 |             aint[nod] = val;
      |                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<int, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from 'int' to 'std::conditional<true, const std::pair<int, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<int, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<int, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from 'int' to 'std::conditional<true, std::pair<int, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<int, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
bubblesort2.cpp:33:25: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
   33 |             aint[nod] = val;
      |                         ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = int; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
bubblesort2.cpp:33:25: note:   mismatched types 'std::pair<_T1, _T2>' and 'int'
   33 |             aint[nod] = val;
      |                         ^~~
bubblesort2.cpp:34:56: error: no matching function for call to 'merge(__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type&)'
   34 |             aint[nod/2] = merge(aint[nod] , aint[nod^1]);
      |                                                        ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter)'
 4944 |     merge(_InputIterator1 __first1, _InputIterator1 __last1,
      |     ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4944:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:34:56: note:   candidate expects 5 arguments, 2 provided
   34 |             aint[nod/2] = merge(aint[nod] , aint[nod^1]);
      |                                                        ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter, class _Compare> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare)'
 4995 |     merge(_InputIterator1 __first1, _InputIterator1 __last1,
      |     ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4995:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:34:56: note:   candidate expects 6 arguments, 2 provided
   34 |             aint[nod/2] = merge(aint[nod] , aint[nod^1]);
      |                                                        ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator, _Compare)'
  412 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
      | ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note:   template argument deduction/substitution failed:
bubblesort2.cpp:34:56: note:   candidate expects 7 arguments, 2 provided
   34 |             aint[nod/2] = merge(aint[nod] , aint[nod^1]);
      |                                                        ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator)'
  417 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
      | ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note:   template argument deduction/substitution failed:
bubblesort2.cpp:34:56: note:   candidate expects 6 arguments, 2 provided
   34 |             aint[nod/2] = merge(aint[nod] , aint[nod^1]);
      |                                                        ^
bubblesort2.cpp: In member function 'void AINT::upd(int, int, int, int, int, int)':
bubblesort2.cpp:52:54: error: no matching function for call to 'merge(__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type&, __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type&)'
   52 |         aint[nod] = merge(aint[2*nod] , aint[2*nod+1]);
      |                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter)'
 4944 |     merge(_InputIterator1 __first1, _InputIterator1 __last1,
      |     ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4944:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:52:54: note:   candidate expects 5 arguments, 2 provided
   52 |         aint[nod] = merge(aint[2*nod] , aint[2*nod+1]);
      |                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter, class _Compare> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare)'
 4995 |     merge(_InputIterator1 __first1, _InputIterator1 __last1,
      |     ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4995:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:52:54: note:   candidate expects 6 arguments, 2 provided
   52 |         aint[nod] = merge(aint[2*nod] , aint[2*nod+1]);
      |                                                      ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator, _Compare)'
  412 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
      | ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note:   template argument deduction/substitution failed:
bubblesort2.cpp:52:54: note:   candidate expects 7 arguments, 2 provided
   52 |         aint[nod] = merge(aint[2*nod] , aint[2*nod+1]);
      |                                                      ^
In file included from /usr/include/c++/10/algorithm:74,
                 from /usr/include/c++/10/ext/pb_ds/hash_policy.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/standard_policies.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:47,
                 from bubblesort2.cpp:2:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator)'
  417 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
      | ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note:   template argument deduction/substitution failed:
bubblesort2.cpp:52:54: note:   candidate expects 6 arguments, 2 provided
   52 |         aint[nod] = merge(aint[2*nod] , aint[2*nod+1]);
      |                                                      ^
bubblesort2.cpp: In member function 'int AINT::mergeAint(std::pair<int, int>, int, std::pair<int, int>, int)':
bubblesort2.cpp:77:20: error: cannot convert 'std::pair<int, int>' to 'int' in return
   77 |             return a1;
      |                    ^~
bubblesort2.cpp:79:21: error: cannot convert 'std::pair<int, int>' to 'int' in return
   79 |         else return a2;
      |                     ^~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:94:15: error: 'vals' was not declared in this scope
   94 |     AINT aint(vals.size());
      |               ^~~~
bubblesort2.cpp:105:23: error: no match for 'operator<' (operand types are 'int' and 'std::map<int, std::priority_queue<int> >')
  105 |     for (int i = 0; i < q; i++)
      |                     ~ ^ ~
      |                     |   |
      |                     int std::map<int, std::priority_queue<int> >
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:489:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  489 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:489:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:105:25: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
  105 |     for (int i = 0; i < q; i++)
      |                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:366:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  366 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:366:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:105:25: note:   mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
  105 |     for (int i = 0; i < q; i++)
      |                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:404:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  404 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:404:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:105:25: note:   mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
  105 |     for (int i = 0; i < q; i++)
      |                         ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from bubblesort2.h:1,
                 from bubblesort2.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr