| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1015627 | nam6 | Radio Towers (IOI22_towers) | 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 "towers.h"
#include<bits/stdc++.h>
using namespace std;
int sommet;
vector<int> altitudes;
vector< pair<int, int> > intervalle;
set<int> choisis;
const int DECA = 1<<17;
int arbre[2*DECA];
void modif(int pos, int val){
pos+=DECA;
arbre[pos] = val;
while(pos > 1){
pos/=2;
arbre[pos] = max(arbre[2*pos], arbre[2*pos+1]);
}
}
int calcMax(int deb, int fin){
if(deb==fin)
return arbre[fin];
if(deb%2==1)
return max(arbre[deb], calcMax(deb+1, fin));
if(fin%2==0)
return max(calcMax(deb, fin-1), fin);
return calcMax(deb/2, fin/2);
}
void init(int N, vector<int> H) {
altitudes = H;
}
int max_towers(int L, int R, int D) {
for(int pos=L; pos<=R; pos++){
intervalle.push_back({altitudes[pos],pos});
modif(pos, altitudes[pos]);
}
sort(intervalle.begin(), intervalle.end());
for(int i=0; i<intervalle.size(); i++){
bool estOk = true;
if(intervalle[i].second > choisis.begin()){
auto igauche = choisis.lower_bound(intervalle[i].second);
igauche--;
int gauche = *igauche;
int maxiGauche = calcMax(gauche + DECA, intervalle[i].second+DECA);
if(maxiGauche - intervalle[i].first < D){
estOk = false;
}
}
if(intervalle[i].second < choisis.rbegin()){
auto idroite = choisis.lower_bound(intervalle[i].second);
int droite = *idroite;
int maxiDroite = calcMax(intervalle[i].second+DECA, droite+DECA);
if(maxiDroite-intervalle[i].first < D){
estOk = false;
}
}
if(estOk){
choisis.insert(intervalle[i].second);
}
}
return choisis.size();
}
Compilation message (stderr)
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:42:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0; i<intervalle.size(); i++){
| ~^~~~~~~~~~~~~~~~~~
towers.cpp:45:29: error: no match for 'operator>' (operand types are 'int' and 'std::set<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'})
45 | if(intervalle[i].second > choisis.begin()){
| ^ ~~~~~~~~~~~~~~~
| |
| std::set<int>::iterator {aka std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator}
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1108:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1108 | operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1108:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1168: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>&)'
1168 | operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1168:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1261: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>&)'
1261 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1261:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1335: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>&)'
1335 | operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1335:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: 'std::set<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1429: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*)'
1429 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1429:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1505: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>&)'
1505 | operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1505:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: 'std::set<int>::iterator' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from towers.cpp:2:
/usr/include/c++/10/bits/regex.h:1605: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&)'
1605 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1605:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:502:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
502 | operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:502:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:378:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
378 | operator>(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:378:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:416:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
416 | operator>(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:416:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1469 | operator>(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1519 | operator>(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/vector:67,
from towers.h:1,
from towers.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1943:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator>(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)'
1943 | operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1943:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::vector<_Tp, _Alloc>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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 towers.cpp:2:
/usr/include/c++/10/string_view:563:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
563 | operator> (basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:563:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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 towers.cpp:2:
/usr/include/c++/10/string_view:569:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >)'
569 | operator> (basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:569:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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 towers.cpp:2:
/usr/include/c++/10/string_view:576:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)'
576 | operator> (__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:576:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: 'std::_Rb_tree_const_iterator<int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
45 | if(intervalle[i].second > choisis.begin()){
| ^
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 towers.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6305:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6305 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6305:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
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 towers.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6318:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
6318 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6318:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
45 | if(intervalle[i].second > choisis.begin()){
| ^
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 towers.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6330:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6330 | operator>(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6330:5: note: template argument deduction/substitution failed:
towers.cpp:45:45: note: mismatched types 'const _CharT*' and 'int'
45 | if(intervalle[i].secon