Submission #1106509

#TimeUsernameProblemLanguageResultExecution timeMemory
1106509Noname_1900Nile (IOI24_nile)C++17
Compilation error
0 ms0 KiB
#include "nile.h" using namespace std; #include<bits/stdc++.h> const int NMAX = 100000; #define int long long const int INFINI = 1000000000000ll; struct T { int normal, enPair; T(int a = 0, int b = 0) { normal = a; enPair = b; } }; vector<pair<int, pair<int, int>>> aretes; int boss[NMAX]; int minRouge[NMAX], minNoir[NMAX]; pair<int, T> infos[NMAX];//W, A, B int sommeB[NMAX]; int sommeTotal; int taille[NMAX]; int sommeComposante[NMAX]; int findBoss(int noeud) { if(boss[noeud] == noeud) { return noeud; } return boss[noeud] = findBoss(boss[noeud]); } void comparerBalance(int noeud) { minRouge[findBoss(noeud)] = min(minRouge[findBoss(noeud)], (infos[noeud].second.normal-infos[noeud].second.enPair)); minNoir[findBoss(noeud)] = min(minNoir[findBoss(noeud)], (infos[noeud].second.normal-infos[noeud].second.enPair)); } void faire(int bossA, int bossB, bool inverserCouleur) { if(inverserCouleur) { minRouge[bossA] = min(minRouge[bossA], minNoir[bossB]); minNoir[bossA] = min(minNoir[bossA], minRouge[bossB]); } else { minRouge[bossA] = min(minRouge[bossA], minRouge[bossB]); minNoir[bossA] = min(minNoir[bossA], minNoir[bossB]); } } void merge(int a, int b) { int bossA = findBoss(a), bossB = findBoss(b); if(bossA == bossB) { int balance = a+1; comparerBalance(balance); sommeTotal -= sommeComposante[bossA]; } else { int debutB = bossB%2; int debutA = bossA%2; int finA = (debutA + taille[bossA]-1)%2; if(finA == debutB) faire(bossA, bossB, 1); else { faire(bossA, bossB, 0); } sommeB[bossA] += sommeB[bossB]; taille[bossA] += taille[bossB]; sommeTotal -= sommeComposante[bossA] + sommeComposante[bossB]; boss[bossB] = bossA; } int noeud = bossA; if(taille[noeud]%2 == 0) { sommeComposante[noeud] = sommeB[noeud]; } else if(bossA%2 == 0) { sommeComposante[noeud] = sommeB[noeud]+minRouge[noeud]; } else { sommeComposante[noeud] = sommeB[noeud]+minNoir[noeud]; } sommeTotal += sommeComposante[noeud]; } pair<int, int> requetes[NMAX]; #undef int std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { #define int long long sommeTotal = 0; int Q = (int)E.size(); int N = W.size(); for(int i = 0; i < Q; i++) { requetes[i] = {E[i], i}; } sort(requetes, requetes+Q); for(int i = 0; i < N; i++) { infos[i] = {W[i], T(A[i], B[i])}; } sort(infos, infos+N); for(int i = 1; i < N; i++) { aretes.push_back({infos[i].first-infos[i-1].first, pair<int, int>(i-1, i)}); if(i >= 2) aretes.push_back({infos[i].first-infos[i-2].first, pair<int, int>(i-2, i)}); } sort(aretes.begin(), aretes.end()); //aVoir for(int i = 0; i < N; i++) { boss[i] = i; taille[i] = 1; sommeTotal += infos[i].second.normal; sommeB[i] = infos[i].second.enPair; sommeComposante[i] = infos[i].second.normal; if(i % 2 == 0) { minRouge[i] = (infos[i].second.normal - infos[i].second.enPair); minNoir[i] = INFINI; } else { minNoir[i] = (infos[i].second.normal- infos[i].second.enPair); minRouge[i] = INFINI; } } std::vector<long long> R(Q); int iEnlever = 0; for(int i = 0; i < Q; i++) { int D = requetes[i].first; while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D)) { merge(aretes[iEnlever].second.first, aretes[iEnlever].second.second); iEnlever++; } R[requetes[i].second] = sommeTotal; } return R; } /** */

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:147:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     while((iEnlever < aretes.size()) && (aretes[iEnlever].first <= D))
      |            ~~~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h: In instantiation of 'constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&) [with _T1 = long long int; _T2 = T]':
/usr/include/c++/10/bits/predefined_ops.h:43:23:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = std::pair<long long int, T>*; _Iterator2 = std::pair<long long int, T>*]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = std::pair<long long int, T>*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::pair<long long int, T>*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = std::pair<long long int, T>*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::pair<long long int, T>*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18:   required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = std::pair<long long int, T>*]'
nile.cpp:110:22:   required from here
/usr/include/c++/10/bits/stl_pair.h:491:50: error: no match for 'operator<' (operand types are 'const T' and 'const T')
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
/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:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::pair<_T1, _T2>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.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:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::reverse_iterator<_Iterator>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.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:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::reverse_iterator<_Iterator>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1451 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1451:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::move_iterator<_IteratorL>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1507:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1507 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1507:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::move_iterator<_IteratorL>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:67,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1930:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)'
 1930 |     operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1930:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::vector<_Tp, _Alloc>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
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 nile.cpp:3:
/usr/include/c++/10/string_view:544:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator<(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
  544 |     operator< (basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:544:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'T' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
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 nile.cpp:3:
/usr/include/c++/10/string_view:550: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> >)'
  550 |     operator< (basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:550:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'T' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
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 nile.cpp:3:
/usr/include/c++/10/string_view:557: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>)'
  557 |     operator< (__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:557:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'T' is not derived from 'std::basic_string_view<_CharT, _Traits>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
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 nile.cpp:3:
/usr/include/c++/10/bits/basic_string.h:6267: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>&)'
 6267 |     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6267:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
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 nile.cpp:3:
/usr/include/c++/10/bits/basic_string.h:6280:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 6280 |     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6280:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   'const T' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
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 nile.cpp:3:
/usr/include/c++/10/bits/basic_string.h:6292:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6292 |     operator<(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6292:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:491:50: note:   mismatched types 'const _CharT*' and 'T'
  491 |       || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                       ~~~~~~~~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/ios_base.h:46,
                 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 nile.cpp:3:
/usr/include/c++/10/system_error:252:3: note: candidate: 'bool std::operator<(const std::error_code&, const std::error_code&)'
  252 |   operator<(const error_code& __lhs, const error_code& __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/10/system_error:252:31: note:   no known conversion for argument 1 from 'const T' to 'const std::error_code&'
  252 |   operator<(const error_code& __lhs, const error_code& __rhs) noexcept
      |             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/system_error:379:3: note: candidate: 'bool std::operator<(const std::error_condition&, const std::error_condition&)'
  379 |   operator<(const error_condition& __lhs,
      |   ^~~~~~~~
/usr/include/c++/10/system_error:379:36: note:   no known conversion for argument 1 from 'const T' to 'const std::error_condition&'
  379 |   operator<(const error_condition& __lhs,
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/10/tuple:39,
                 from /usr/include/c++/10/functional:54,