Submission #887864

#	Time	Username	Problem	Language	Result	Execution time	Memory
887864		1L1YA	Rainforest Jumps (APIO21_jumps)	C++17	27 / 100	1204 ms	47744 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],sp1[lg][N],sp2[lg][N];
    pii seg[N<<2];
     
    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);
        if(seg[lc].F>seg[rc].F)    seg[id]=seg[lc];
        else    seg[id]=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;
        pii p1=get(ql,qr,lc,l,mid),p2=get(ql,qr,rc,mid,r);
        if(p1.F>p2.F)     return p1;
        else    return p2;
    }
     
    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).F;
        if(get(r1,l2).F>mx)
            return -1;
        int x=get(l1,r1+1).S;
        mx=get(l1,l2).F;
        int l=l2-1,r=r2;
        while(r-l>1){
            int mid=l+r>>1;
            if(get(l2,mid+1).F<mx)    l=mid;
            else    r=mid;
        }
        int ans=dist(a[x],a[r]);
        if(get(1,l2).F>mx){
            l=0,r=l2;
            while(r-l>1){
                int mid=l+r>>1;
                if(get(mid,l2).F<mx)    r=mid;
                else    l=mid;
            }
            if(l){
                ans=min(ans,dist(a[x],a[l])+1);
            }
        }
        return ans;
    }

Compilation message (stderr)

jumps.cpp: In function 'void modify(int, int, int, int, int)':
jumps.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid=l+r>>1;
      |                 ~^~
jumps.cpp: In function 'std::pair<int, int> get(int, int, int, int, int)':
jumps.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int mid=l+r>>1;
      |                 ~^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:102:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int mid=l+r>>1;
      |                     ~^~
jumps.cpp:110:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |                 int mid=l+r>>1;
      |                         ~^~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 23 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19