| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 939644 | 2024-03-06T15:58:58 Z | haxorman | Dancing Elephants (IOI11_elephants) | C++14 | Compilation error |
0 ms | 0 KB |
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 150007;
const int SZ = 388;
int n, l, step, pos[mxN], bkt[mxN], to[mxN], cnt[mxN], sz[SZ];
set<pair<int,int>> st;
vector<pair<int,int>> arr[mxN];
void fix(int b) {
for (int i = arr[b].size()-1; i >= 0; --i) {
int val = arr[b][i].first + l;
if (val >= arr[b].back()) {
to[arr[b][i].second] = val;
cnt[arr[b][i].second] = 1;
}
else {
auto it = upper_bound(arr[b].begin(), arr[b].end(),
make_pair(val,INT_MAX));
to[arr[b][i].second] = to[(*it).second];
cnt[arr[b][i].second] = cnt[(*it).second] + 1;
}
}
}
void construct() {
for (int i = 0; i < SZ; ++i) {
arr[i].clear();
}
auto it = st.begin();
for (int i = 0; i < n; ++i) {
bkt[(*it).second] = i/SZ;
arr[i/SZ].push_back(*it);
advance(it, 1);
}
for (int b = 0; b < SZ; ++b) {
fix(b);
}
}
void init(int N, int L, int X[]) {
n = N, l = L;
for (int i = 0; i < n; ++i) {
pos[i] = X[i];
st.insert({pos[i], i});
}
construct();
}
int update(int i, int y) {
for (int j = 0; j < arr[bkt[i]].size(); ++j) {
if (arr[bkt[i]][j].second == i) {
arr[bkt[i]].erase(arr[bkt[i]].begin() + j);
break;
}
}
st.erase({pos[i], i});
fix(bkt[i]);
for (int b = 0; b < SZ; ++b) {
if (b == SZ-1 || (arr[b].size() && arr[b].back().first > y)) {
bkt[i] = b;
arr[b].push_back({pos[i] = y, i});
sort(arr[b].begin(), arr[b].end());
st.insert({pos[i], i});
fix(b);
break;
}
}
int ans = 0, cur = -1;
for (int b = 0; b < SZ; ++b) {
if (arr[b].size() && arr[b].back().first > cur) {
auto it = upper_bound(arr[b].begin(), arr[b].end(),
make_pair(cur,INT_MAX));
ans += cnt[(*it).second];
cur = to[(*it).second];
}
}
step++;
if (step == SZ) {
construct();
step = 0;
}
return ans;
}
Compilation message
elephants.cpp: In function 'void fix(int)':
elephants.cpp:16:17: error: no match for 'operator>=' (operand types are 'int' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'})
16 | if (val >= arr[b].back()) {
| ~~~ ^~ ~~~~~~~~~~~~~
| | |
| int __gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type {aka std::pair<int, int>}
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1097:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>=(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1097 | operator>=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1097:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1180: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>&)'
1180 | operator>=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1180:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1273: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>&)'
1273 | operator>=(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1273:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1347: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>&)'
1347 | operator>=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1347:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1441: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*)'
1441 | operator>=(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1441:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1518: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>&)'
1518 | operator>=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1518:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'std::pair<int, int>'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/10/bits/regex.h:1618: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&)'
1618 | operator>=(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1618:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:514:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
514 | operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:514:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:390:5: note: candidate: 'template<class _Iterator> bool std::operator>=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
390 | operator>=(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:390:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:428:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator>=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
428 | operator>=(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:428:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1478:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator>=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1478 | operator>=(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1478:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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 elephants.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1525:5: note: candidate: 'template<class _Iterator> bool std::operator>=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1525 | operator>=(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1525:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
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 elephants.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6381:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
6381 | operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6381:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
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 elephants.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6394:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>=(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)'
6394 | operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6394:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
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 elephants.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6406:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>=(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
6406 | operator>=(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6406:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const _CharT*' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/deque:67,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
from elephants.cpp:2:
/usr/include/c++/10/bits/stl_deque.h:2304:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator>=(const std::deque<_Tp, _Alloc>&, const std::deque<_Tp, _Alloc>&)'
2304 | operator>=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:2304:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::deque<_Tp, _Alloc>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/tuple:39,
from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from elephants.cpp:2:
/usr/include/c++/10/array:305:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> bool std::operator>=(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&)'
305 | operator>=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
| ^~~~~~~~
/usr/include/c++/10/array:305:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::array<_Tp, _Nm>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from elephants.cpp:2:
/usr/include/c++/10/tuple:1466:5: note: candidate: 'template<class ... _TElements, class ... _UElements> constexpr bool std::operator>=(const std::tuple<_Tps ...>&, const std::tuple<_Elements ...>&)'
1466 | operator>=(const tuple<_TElements...>& __t,
| ^~~~~~~~
/usr/include/c++/10/tuple:1466:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::tuple<_Tps ...>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/locale_conv.h:41,
from /usr/include/c++/10/locale:43,
from /usr/include/c++/10/iomanip:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:72,
from elephants.cpp:2:
/usr/include/c++/10/bits/unique_ptr.h:872:5: note: candidate: 'template<class _Tp, class _Dp, class _Up, class _Ep> bool std::operator>=(const std::unique_ptr<_Tp, _Dp>&, const std::unique_ptr<_Up, _Ep>&)'
872 | operator>=(const unique_ptr<_Tp, _Dp>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/unique_ptr.h:872:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::unique_ptr<_Tp, _Dp>' and 'int'
16 | if (val >= arr[b].back()) {
| ^
In file included from /usr/include/c++/10/bits/locale_conv.h:41,
from /usr/include/c++/10/locale:43,
from /usr/include/c++/10/iomanip:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:72,
from elephants.cpp:2:
/usr/include/c++/10/bits/unique_ptr.h:879:5: note: candidate: 'template<class _Tp, class _Dp> bool std::operator>=(const std::unique_ptr<_Tp, _Dp>&, std::nullptr_t)'
879 | operator>=(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
| ^~~~~~~~
/usr/include/c++/10/bits/unique_ptr.h:879:5: note: template argument deduction/substitution failed:
elephants.cpp:16:32: note: mismatched types 'const std::un