| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 346260 | casperwang | Dancing Elephants (IOI11_elephants) | C++14 | 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 "elephants.h"
#include <bits/stdc++.h>
#pragma gcc optimize("Ofast")
#define pb push_back
#define All(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int MAXN = 150000;
const int INF = 1e9;
const int K = 390;
int n, m, seg;
int cnt;
vector <pii> a;
vector <vector<pii>> B;
vector <pii> rng;
vector <int> pos;
vector <pii> info;
void build_block(int id, bool flag) {
int len = B[id].size();
if (!len) {
rng[id] = pii(id==0 ? -INF : rng[id-1].ss, id==m-1 ? INF : rng[id+1].ff);
return;
}
if (flag) sort(All(B[id]));
int nowR = len-1;
for (int i = len-1; i >= 0; i--) {
pos[B[id][i].ss] = id;
if (B[id][i].ff + seg >= B[id][len-1].ff) {
info[B[id][i].ss] = pii(1, B[id][i].ff + seg);
} else {
while (nowR && B[id][i].ff + seg < B[id][nowR-1].ff) nowR--;
info[B[id][i].ss] = pii(info[B[id][nowR].ss].ff + 1, info[B[id][nowR].ss].ss);
}
}
rng[id] = pii(B[id][0].ff, B[id][len-1].ff);
}
void build() {
sort(All(a));
for (int i = 0; i < m; i++)
B[i].clear();
for (int i = 0; i < n; i++)
B[i/K].pb(a[i]);
for (int i = 0; i < m; i++)
build_block(i, false);
sort(All(a), [](const pii x, const pii y) {
return x.ss < y.ss;
});
}
int solve() {
int ans = 0, now = -1;
for (int i = 0; i < m; i++) {
auto tmp = upper_bound(All(B[i]), pii(now, n+1));
if (tmp == B[i].end()) continue;
ans += info[tmp->ss].ff;
now = info[tmp->ss].ss;
}
return ans;
}
void init(int N, int L, int X[]) {
cnt = 0;
n = N, m = (n-1)/K+1, seg = L;
a.clear(), a.resize(n);
pos.clear(), pos.resize(n);
info.clear(), info.resize(n);
B.clear(), B.resize(m);
rng.clear(), rng.resize(m);
for (int i = 0; i < n; i++)
a[i].ff = X[i], a[i].ss = i;
build();
}
int update(int i, int y) {
cnt++;
a[i].ff = y;
if (cnt % (K+150) == 0) build();
int id = pos[i];
for (int j = 0; j < (int)B[id].size(); j++) {
if (B[id][j].ss == i) {
B[id].erase(B[id].begin()+j);
break;
}
}
build_block(id, false);
vector <int> sav;
for (int j = 0; j < m; j++) {
if ((!j || rng[j-1].ss <= y) && (j==m-1 || rng[j+1].ff >= y)) {
sav.pb(j);
}
}
sort(All(sav), [&](const int x, const int y) {
return B[x].size() < B[y].size();
});
B[sav[0]].pb(a[i]);
pos[i] = sav[0];
build_block(sav[0], a[i] < rng[sav[0]].ss);
return solve();
}
Compilation message (stderr)
elephants.cpp:3: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
3 | #pragma gcc optimize("Ofast")
|
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:106:28: 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')
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1048:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1048 | operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1048:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1124: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>&)'
1124 | operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1124:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1198: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>&)'
1198 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1198:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1272: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>&)'
1272 | operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1272:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1346: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*)'
1346 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1346:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1421: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>&)'
1421 | operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1421:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: note: mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/regex:62,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:110,
from elephants.cpp:2:
/usr/include/c++/9/bits/regex.h:1499: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&)'
1499 | operator<(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/regex.h:1499:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/stl_pair.h:454:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
454 | operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:454:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: note: mismatched types 'const std::pair<_T1, _T2>' and 'int'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:331:5: note: candidate: 'template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
331 | operator<(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:331:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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::reverse_iterator<_Iterator>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:369:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
369 | operator<(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:369:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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::reverse_iterator<_Iterator>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:1163:5: note: candidate: 'template<class _IteratorL, class _IteratorR> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1163 | operator<(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1163:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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::move_iterator<_IteratorL>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/bits/stl_algobase.h:67,
from /usr/include/c++/9/bits/char_traits.h:39,
from /usr/include/c++/9/ios:40,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/stl_iterator.h:1169:5: note: candidate: 'template<class _Iterator> bool std::operator<(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1169 | operator<(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/9/bits/stl_iterator.h:1169:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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::move_iterator<_IteratorL>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/basic_string.h:6226: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>&)'
6226 | operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6226:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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::basic_string<_CharT, _Traits, _Alloc>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/basic_string.h:6239:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _CharT*)'
6239 | operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6239:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: 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::basic_string<_CharT, _Traits, _Alloc>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/string:55,
from /usr/include/c++/9/bits/locale_classes.h:40,
from /usr/include/c++/9/bits/ios_base.h:41,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/bits/basic_string.h:6251:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator<(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
6251 | operator<(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/9/bits/basic_string.h:6251:5: note: template argument deduction/substitution failed:
elephants.cpp:8:12: note: mismatched types 'const _CharT*' and 'std::pair<int, int>'
8 | #define ss second
| ^~~~~~
elephants.cpp:106:42: note: in expansion of macro 'ss'
106 | build_block(sav[0], a[i] < rng[sav[0]].ss);
| ^~
In file included from /usr/include/c++/9/bits/ios_base.h:46,
from /usr/include/c++/9/ios:42,
from /usr/include/c++/9/istream:38,
from /usr/include/c++/9/sstream:38,
from /usr/include/c++/9/complex:45,
from /usr/include/c++/9/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
from elephants.cpp:2:
/usr/include/c++/9/system_error:208:3: note: candidate: 'bool std::operator<(const std::error_code&, const std::error_code&)'
208 | operator<(const error_code& __lhs, const error_code& __rhs) noexcept
| ^~~~~~~~
/usr/include/c++/9/system_error:208:31: note: no known conversion for argument 1 from '__gnu_cxx::__alloc_traits<std::allocator<std::pair<i