Submission #887885

#	Time	Username	Problem	Language	Result	Execution time	Memory
887885		1L1YA	Rainforest Jumps (APIO21_jumps)	C++17	Compilation error	0 ms	0 KiB

jumps

//1L1YA
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define Pb           push_back
#define dokme(x)     cout << x << endl, exit(0)
#define pii          pair<int,int>
#define F            first
#define S            second
#define endl         '\n'
#define sep          ' '
#define all(x)       x.begin(),x.end()
#define FastIO       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lc           id<<1
#define rc           lc|1

const int N=2e5+5;
const int lg=23;

int n,a[N],lst[N],nxt[N],seg[N<<2],sp1[lg][N],sp2[lg][N];

void modify(int pos,int val,int id=1,int l=1,int r=n+1){
    if(r-l==1){
        seg[id]={val,pos};
        return;
    }
    int mid=l+r>>1;
    if(pos<mid)    modify(pos,val,lc,l,mid);
    else    modify(pos,val,rc,mid,r);
    seg[id]=max(seg[lc],seg[rc]);
}

pii get(int ql,int qr,int id=1,int l=1,int r=n+1){
    if(qr<=l || ql>=r)    return {0,0};
    if(ql<=l && r<=qr)    return seg[id];
    int mid=l+r>>1;
    return max(get(ql,qr,lc,l,mid),get(ql,qr,rc,mid,r));
}

void init(int m, std::vector<int> h) {
    n=m;
    for(int i=1;i<=n;i++)
        a[i]=h[i-1];
    a[0]=a[n+1]=n+1;
    vector<int> st;
    st.Pb(0);
    for(int i=1;i<=n;i++){
        while(a[st.back()]<a[i])
            st.pop_back();
        lst[i]=st.back();
        st.Pb(i);
    }
    st.clear();
    st.Pb(n+1);
    for(int i=n;i;i--){
        while(a[st.back()]<a[i])
            st.pop_back();
        nxt[i]=st.back();
        st.Pb(i);
    }
    for(int i=1;i<=n;i++){
        sp1[0][a[i]]=min(a[lst[i]],a[nxt[i]]);
        sp2[0][a[i]]=max(a[lst[i]],a[nxt[i]]);
    }
    sp1[0][n+1]=sp2[0][n+1]=n+1;
    for(int i=n+1;i;i--)
        for(int j=1;j<lg;j++){
            sp1[j][i]=sp1[j-1][sp1[j-1][i]];
            sp2[j][i]=sp2[j-1][sp2[j-1][i]];
        }
    for(int i=1;i<=n;i++)
        modify(i,a[i]);
}

int dist(int s,int e){
    int ans=0;
    for(int i=lg-1;~i;i--)
        if(sp2[i][s]<e)
            s=sp2[i][s],ans+=1<<i;
    if(sp2[0][s]==e)
        return ans+1;
    for(int i=lg-1;~i;i--)
        if(sp1[i][s]<e)
            s=sp1[i][s],ans+=1<<i;
    return ans+1;
}

int minimum_jumps(int l1, int r1, int l2, int r2){
    l1++;r1++;l2++;r2++;
    int mx=get(l2,r2+1);
    if(get(r1,l2).F>mx)
        return -1;
    int l=0,r=r1;
    while(r-l>1){
        int mid=l+r>>1;
        if(get(mid,r1+1)<mx)    r=mid;
        else    l=mid;
    }
    int k=r,x=get(max(l1,k),r1+1);
    mx=get(max(l1,k),l2);
    int ans=dist(x,mx)+1;
    if(k<=l1){
        l=1,r=l1;
        while(r-l>1){
            int mid=l+r>>1;
            if(get(mid,l1)<mx)    r=mid;
            else    l=mid;
        }
        if(l>k)
            ans=min(ans,dist(x,a[l])+1);
    }
    return ans;
}
/*
int main() {
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}*/

Compilation message (stderr)

jumps.cpp: In function 'void modify(int, int, int, int, int)':
jumps.cpp:25:25: error: cannot convert '<brace-enclosed initializer list>' to 'int' in assignment
   25 |         seg[id]={val,pos};
      |                         ^
jumps.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid=l+r>>1;
      |             ~^~
jumps.cpp: In function 'std::pair<int, int> get(int, int, int, int, int)':
jumps.cpp:36:40: error: could not convert 'seg[id]' from 'int' to 'std::pair<int, int>'
   36 |     if(ql<=l && r<=qr)    return seg[id];
      |                                  ~~~~~~^
      |                                        |
      |                                        int
jumps.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid=l+r>>1;
      |             ~^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:91:15: error: cannot convert 'std::pair<int, int>' to 'int' in initialization
   91 |     int mx=get(l2,r2+1);
      |            ~~~^~~~~~~~~
      |               |
      |               std::pair<int, int>
jumps.cpp:96:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         int mid=l+r>>1;
      |                 ~^~
jumps.cpp:97:25: error: no match for 'operator<' (operand types are 'std::pair<int, int>' and 'int')
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |            ~~~~~~~~~~~~~^~~
      |               |          |
      |               |          int
      |               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 jumps.cpp:3:
/usr/include/c++/10/bits/regex.h:1075:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator<(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1075 |     operator<(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1075:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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:3:
/usr/include/c++/10/bits/regex.h:1156: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>&)'
 1156 |     operator<(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1156:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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:3:
/usr/include/c++/10/bits/regex.h:1249: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>&)'
 1249 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1249:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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:3:
/usr/include/c++/10/bits/regex.h:1323: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>&)'
 1323 |     operator<(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1323:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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:3:
/usr/include/c++/10/bits/regex.h:1417: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*)'
 1417 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1417:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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:3:
/usr/include/c++/10/bits/regex.h:1492: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>&)'
 1492 |     operator<(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1492:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   mismatched types 'const std::__cxx11::sub_match<_BiIter>' and 'int'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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:3:
/usr/include/c++/10/bits/regex.h:1592: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&)'
 1592 |     operator<(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1592:5: note:   template argument deduction/substitution failed:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:2:
/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:
jumps.cpp:97:26: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:2:
/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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:2:
/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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:2:
/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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::move_iterator<_IteratorL>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from jumps.h:1,
                 from jumps.cpp:2:
/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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::move_iterator<_IteratorL>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
In file included from /usr/include/c++/10/vector:67,
                 from jumps.h:1,
                 from jumps.cpp:2:
/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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::vector<_Tp, _Alloc>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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: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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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: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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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: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:
jumps.cpp:97:26: note:   mismatched types 'std::basic_string_view<_CharT, _Traits>' and 'int'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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: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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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: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:
jumps.cpp:97:26: note:   'std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   97 |         if(get(mid,r1+1)<mx)    r=mid;
      |                          ^~
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: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: