| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 884121 | vjudge1 | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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