Submission #860211

#	Time	Username	Problem	Language	Result	Execution time	Memory
860211		nnhzzz	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	861 ms	45944 KiB

jumps

// cre: Nguyen Ngoc Hung - Train VOI 2024 :>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <array>
#include <cassert>
#include <random>

using namespace std;

#define        __nnhzzz__  signed main()
#define          BIT(i,j)  ((i>>j)&1LL)
#define           MASK(i)  (1LL<<i)
#define            ALL(x)  (x).begin(),(x).end()
#define             SZ(x)  (int)(x).size()
#define                fi  first
#define                se  second
#define                ll  long long
#define                vi  vector<int>
#define               vvi  vector<vi>
#define               pii  pair<int,int>
#define              vpii  vector<pii>
#define REPDIS(i,be,en,j)  for(int i = (be); i<=(en); i+=j)
#define     REPD(i,be,en)  for(int i = (be); i>=(en); i--)
#define      REP(i,be,en)  for(int i = (be); i<=(en); i++)
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 18,MAXN = 2e5+77,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; }
template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; }

/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Nguyen Ngoc Hung - nnhzzz
    Training for VOI24 gold medal
----------------------------------------------------------------
*/

int a[MAXN],hi[MAXN][LOG],rgt[MAXN][LOG],ma[MAXN][LOG];
int n;

#define combine(x,y) (a[(x)]<a[(y)]?(y):(x))

int get(int l, int r){
    int k = __lg(r-l+1);
    return combine(ma[l][k],ma[r-MASK(k)+1][k]);
}

bool F(int i, int l, int r){
    return (i>=l && i<=r);
}

void init(int N, vi arr){
    n = N;
    REP(i,1,n) a[i] = arr[i-1];
    a[0] = a[n+1] = n+1;
    stack<int> st; st.push(0);
    REP(i,1,n){
        while(a[st.top()]<a[i]) st.pop();
        hi[i][0] = st.top(); st.push(i);
    }
    st.push(n+1);
    REPD(i,n,1){
        while(a[st.top()]<a[i]) st.pop();
        rgt[i][0] = st.top(); st.push(i);
    }
    rgt[0][0] = rgt[n+1][0] = n+1;
    REP(i,1,n){
        ma[i][0] = i;
        hi[i][0] = combine(hi[i][0],rgt[i][0]);
    }
    REP(j,1,LOG-1){
        REP(i,0,n+1){
            hi[i][j] = hi[hi[i][j-1]][j-1];
            rgt[i][j] = rgt[rgt[i][j-1]][j-1];
            if(i+MASK(j)-1>n) continue;
            ma[i][j] = combine(ma[i][j-1],ma[i+MASK((j-1))][j-1]);
        }
    }
}

// 3 2 1 6 4 5 7
// 2-4  6-7

int minimum_jumps(int A, int B, int C, int D){
    ++A; ++B; ++C; ++D;
    int CD = get(C,D),BC = get(B,C-1);
    if(a[BC]>a[CD]) return -1;
    int l = A,r = B;
    while(l<=r){
        int mid = (l+r)>>1;
        if(a[get(mid,B)]<a[CD]){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    int pos = get(l,B);
    if(F(rgt[pos][0],C,D)) return 1;
    int res = 0;
    REPD(i,LOG-1,0){
        int newpos = hi[pos][i];
        if(rgt[newpos][0]<C){
            pos = newpos;
            res += MASK(i);
        }
    }
    int newpos = hi[pos][0];
    if(rgt[newpos][0]<=D){
        pos = newpos; ++res;
        if(F(rgt[pos][0],C,D)) return res+1;
    }
    REPD(i,LOG-1,0){
        newpos = rgt[pos][i];
        if(newpos<C){
            pos = newpos;
            res += MASK(i);
        }
    }
    return res+1;
}

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