| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 569626 | Turkhuu | Rainforest Jumps (APIO21_jumps) | 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 "jumps.h"
#include <bits/stdc++.h>
using namespace std;
const int L = 18;
const int inf = 1000000000;
int n;
vector<int> a, lg;
vector<vector<int>> lo, hi, st, g;
bool subtask1 = true;
void init(int N, vector<int> H){
n = N, a = H;
g.resize(n);
lg.resize(n + 1);
lo.assign(n, vector(L, -1));
hi.assign(n, vector(L, -1));
st.assign(n, vector(L, 0));
for(int i = 1; i < n; i++){
if(a[i - 1] > a[i]){
subtask1 = false;
}
}
vector<int> idx(n);
for(int i = 0; i < n; i++){
idx[--a[i]] = i;
}
for(int i = 2; i <= n; i++){
lg[i] = lg[i / 2] + 1;
}
for(int i = 0; i < n; i++){
st[i][0] = a[i];
}
for(int j = 1; j < L; j++){
for(int i = 0; i + (1 << j) - 1 < n; i++){
st[i][j] = max(st[i][j - 1], st[i + (1 << j)][j - 1]);
}
}
set<int> s;
for(int i = n - 1; i >= 0; i--){
auto j = s.lower_bound(idx[i]);
int l = -1, r = -1;
if(j != s.end()){
r = a[*j];
g[idx[i]].push_back(*j);
}
if(j != s.begin()){
l = a[*prev(j)];
g[idx[i]].push_back(*prev(j));
}
if(l != -1 && (r == -1 || l >= r)){
lo[i][0] = r;
hi[i][0] = l;
} else{
lo[i][0] = l;
hi[i][0] = r;
}
s.insert(idx[i]);
}
for(int j = 1; j < L; j++){
for(int i = 0; i < n; i++){
if(lo[i][j - 1] != -1){
lo[i][j] = lo[lo[i][j - 1]][j - 1];
}
if(hi[i][j - 1] != -1){
hi[i][j] = hi[hi[i][j - 1]][j - 1];
}
}
}
}
int minimum_jumps(int A, int B, int C, int D){
if(subtask1){
return C - B;
}
if((n <= 2000 && q <= 2000) || q <= 5){
queue<int> q;
vector<int> d(n, inf);
for(int i = A; i <= B; i++){
d[i] = 0;
q.push(i);
}
while(!q.empty()){
int i = q.front();
q.pop();
if(C <= i && i <= D){
return d[i];
}
for(int j : g[i]){
if(d[i] + 1 < d[j]){
d[j] = d[i] + 1;
q.push(j);
}
}
}
return -1;
}
if(C == D){
int L = lg[B - A + 1];
int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
int G = a[C], c = 0;
for(int i = L - 1; i >= 0; i--){
if(hi[H][i] != -1 && hi[H][i] <= G){
H = hi[H][i];
c += 1 << i;
}
}
for(int i = L - 1; i >= 0; i--){
if(lo[H][i] != -1 && lo[H][i] <= G){
H = lo[H][i];
c += 1 << i;
}
}
if(H != G){
c = -1;
}
return c;
}
return -1;
}
Compilation message (stderr)
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:73:20: error: 'q' was not declared in this scope
73 | if((n <= 2000 && q <= 2000) || q <= 5){
| ^
jumps.cpp:74:16: error: redeclaration of 'std::queue<int> q'
74 | queue<int> q;
| ^
jumps.cpp:73:20: note: '<typeprefixerror>q' previously declared here
73 | if((n <= 2000 && q <= 2000) || q <= 5){
| ^
jumps.cpp:97:22: error: no match for 'operator[]' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::vector<int> >, std::vector<int> >::value_type' {aka 'std::vector<int>'} and 'std::vector<int>')
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^
In file included from /usr/include/c++/10/vector:67,
from jumps.h:1,
from jumps.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1043:7: note: candidate: 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::reference = int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
1043 | operator[](size_type __n) _GLIBCXX_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1043:28: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<int>::size_type' {aka 'long unsigned int'}
1043 | operator[](size_type __n) _GLIBCXX_NOEXCEPT
| ~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1061:7: note: candidate: 'std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) const [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::const_reference = const int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]'
1061 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1061:28: note: no known conversion for argument 1 from 'std::vector<int>' to 'std::vector<int>::size_type' {aka 'long unsigned int'}
1061 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT
| ~~~~~~~~~~^~~
jumps.cpp:97:38: error: no match for 'operator<<' (operand types are 'int' and 'std::vector<int>')
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ~ ^~ ~~
| | |
| int std::vector<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 jumps.cpp:2:
/usr/include/c++/10/bits/regex.h:1647:5: note: candidate: 'template<class _Ch_type, class _Ch_traits, class _Bi_iter> std::basic_ostream<_CharT, _Traits>& std::__cxx11::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::__cxx11::sub_match<_Bi_iter>&)'
1647 | operator<<(basic_ostream<_Ch_type, _Ch_traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1647:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
from jumps.cpp:2:
/usr/include/c++/10/cstddef:125:5: note: candidate: 'template<class _IntegerType> constexpr std::__byte_op_t<_IntegerType> std::operator<<(std::byte, _IntegerType)'
125 | operator<<(byte __b, _IntegerType __shift) noexcept
| ^~~~~~~~
/usr/include/c++/10/cstddef:125:5: note: template argument deduction/substitution failed:
jumps.cpp:97:36: note: cannot convert '1' (type 'int') to type 'std::byte'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^
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 jumps.cpp:2:
/usr/include/c++/10/string_view:622:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, std::basic_string_view<_CharT, _Traits>)'
622 | operator<<(basic_ostream<_CharT, _Traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/string_view:622:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
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 jumps.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6458:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6458 | operator<<(basic_ostream<_CharT, _Traits>& __os,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6458:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
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 jumps.cpp:2:
/usr/include/c++/10/system_error:262:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::error_code&)'
262 | operator<<(basic_ostream<_CharT, _Traits>& __os, const error_code& __e)
| ^~~~~~~~
/usr/include/c++/10/system_error:262:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:506:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, _CharT)'
506 | operator<<(basic_ostream<_CharT, _Traits>& __out, _CharT __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:506:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:511:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char)'
511 | operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:511:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:517:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char)'
517 | operator<<(basic_ostream<char, _Traits>& __out, char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:517:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<char, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:523:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char)'
523 | operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:523:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<char, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:528:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char)'
528 | operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
| ^~~~~~~~
/usr/include/c++/10/ostream:528:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<char, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:589:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const _CharT*)'
589 | operator<<(basic_ostream<_CharT, _Traits>& __out, const _CharT* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:589:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/ostream:784,
from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/bits/ostream.tcc:321:5: note: candidate: 'template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const char*)'
321 | operator<<(basic_ostream<_CharT, _Traits>& __out, const char* __s)
| ^~~~~~~~
/usr/include/c++/10/bits/ostream.tcc:321:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<_CharT, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:606:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const char*)'
606 | operator<<(basic_ostream<char, _Traits>& __out, const char* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:606:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<char, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:619:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const signed char*)'
619 | operator<<(basic_ostream<char, _Traits>& __out, const signed char* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:619:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<char, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:624:5: note: candidate: 'template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const unsigned char*)'
624 | operator<<(basic_ostream<char, _Traits>& __out, const unsigned char* __s)
| ^~~~~~~~
/usr/include/c++/10/ostream:624:5: note: template argument deduction/substitution failed:
jumps.cpp:97:41: note: mismatched types 'std::basic_ostream<char, _Traits>' and 'int'
97 | int H = max(st[A][lg], st[B - (1 << lg) + 1][lg]);
| ^~
In file included from /usr/include/c++/10/istream:39,
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 jumps.cpp:2:
/usr/include/c++/10/ostream:773:5: note: candidate: 'template<class _Ostream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_ostream<_Ostream>, std::__is_insertable<typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type, const _Tp&, void> >::value, typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type>::type std::operator<<(_Ostream&&, const _Tp&)'
773 | operator<<(_Ostream&& __os, const _Tp& __x)
| ^~~~~~~~
/usr/include/c++/10/ostream:773:5: note: template argument deduction/substitution failed:
/usr/include/c++/10/ostream: In substitution of 'template<class _Ostream, class _Tp> typename std::enable_if<std::__and_<std::__not_<std::is_lvalue_reference<_Tp> >, std::__is_convertible_to_basic_ostream<_Ostream>, std::__is_insertable<typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type, const _Tp&, void> >::value, typename std::__is_convertible_to_basic_ostream<_Tp>::__ostream_type>::type std::operator<<(_Ostream&&, const _Tp&) [with _Ostream = int; _Tp = std::vector<int>]':
jumps.cpp:97:41: required from here
/usr/include/c++/10/ostream:773:5: error: no type named 'type' in 'struct std::enable_if<false, void>'
In file included from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from jumps.cpp:2:
/usr/include/c++/10/complex:554:5: note: candidate: 'template<class _Tp, class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::complex<_Tp>&)'
554 | ope