Submission #887824

#	Time	Username	Problem	Language	Result	Execution time	Memory
887824		Danet	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	942 ms	55500 KiB

jumps

/****************************D a N E T****************************
***     ██████╗     █████╗    ███╗    ██╗   ███████╗ ████████╗   ***
***     ██╔══██╗   ██╔══██╗   ████╗   ██║   ██╔════╝ ╚══██╔══╝   ***
***     ██║   ██║  ███████║   ██╔██╗  ██║   █████╗      ██║      ***
***     ██║   ██║  ██╔══██║   ██║╚██╗ ██║   ██╔══╝      ██║      ***
***     ██████╔╝   ██║  ██║   ██║  ╚████║   ███████╗    ██║      ***
***     ╚═════╝    ╚═╝  ╚═╝   ╚═╝   ╚═══╝   ╚══════╝    ╚═╝      ***   
****************************D a N E T****************************/
#include <bits/stdc++.h>
using namespace std;
/**************************P R a G M as**************************/
#pragma Gcc optimize("O3")
/**************************D E F I N Es**************************/
#define Tof_Io  		ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
//#define int  			long long int
#define double  		long double
#define pb				push_back
#define endl 			'\n'
/*****************D E F I N Es-F U N c T I O Nes*****************/
#define debug(x)    	cerr << #x << ": " << x << endl
#define kill(x)     	cout << x << endl, exit(0)
#define all(x) 			x.begin(),x.end()
#define yes             cout << "Yes"
#define no              cout <<"No"
/***************************c O N S Ty***************************/
const double 			PI = 3.141592653589793;
const int 				mod = 998244353;//1e9+7 998244353
const int 				inf = 1e9+9;
const int 				lg = 19;
const int               N = 2e5 + 23;
/***************************b U I L Dy***************************/
int fac[N];
int inv[N];
vector<int> adj[N];

vector<pair<int, int> > dx = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
/****************************N O T Ey****************************/
/*

*/
/***********************F U N c T I O N es***********************/
int  dnt_pow	(int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
void dnt_bld	(){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
int  dnt_ncr	(int n,int r){return fac[n] * inv[r] % mod * inv[n-r] % mod;}
/****************************************************************/ 
int jm[2][20][N];
int er[20][N];
vector<int> h;
int n;

void init(int nn, vector<int> hh) 
{
    stack<int> s;
    n = nn;
    h.push_back(1e9);
    for(int i = 0; i < hh.size(); i++)
    {
        h.push_back(hh[i]);
    }
    h.push_back(1e9);
    n++;
    n++;
    for(int i = 0; i < n; i++)
    {
        while(!s.empty() and (h[s.top()] < h[i]))
        {
            s.pop();
        }
        if(s.empty())
        {
            jm[0][0][i] = i;
        }
        else
        {
            jm[0][0][i] = s.top();
        }
        s.push(i);
    }
    ///
    while(!s.empty())
    {
        s.pop();
    }
    ///
    ///
    ///
    ///
    //

    for(int i = n - 1; i >= 0; i--)
    {
        while(!s.empty() and (h[s.top()] < h[i]))
        {
            s.pop();
        }
        //
        if(s.empty())
        {
            jm[1][0][i] = i;
        }
        else
        {
            jm[1][0][i] = s.top();
        }
        s.push(i);

        ////
        er[0][i] = jm[0][0][i];
        if(h[jm[1][0][i]] >= h[jm[0][0][i]]) er[0][i] = jm[1][0][i];
    }
    //

    for(int i = 1; i < 20; i++)
    {
        for(int j = 0; j < n; j++)
        {
            jm[0][i][j] = jm[0][i - 1][jm[0][i - 1][j]];

            jm[1][i][j] = jm[1][i - 1][jm[1][i - 1][j]];

            er[i][j] = er[i - 1][er[i - 1][j]];
        }
    }
}
 
int minimum_jumps(int a, int b, int c, int d) 
{
    a++, b++, c++, d++;
    if(b + 1 == c)
    {
        if(jm[1][0][b] > d)
        {
            return -1;
        }
        return 1;
    }
    //
    int mid = b + 1;
    for(int i = lg; i >= 0; i--)
    {
        if(jm[1][i][mid] <= c - 1)
        {
            mid = jm[1][i][mid];
        }
    }
    //
    if(h[b] > h[mid])
    {
        if(jm[1][0][b] <= d) return 1;
        return -1;
    }
    int tmp = b;
    for(int i = lg; i >= 0; i--)
    {
        if(a <= jm[0][i][tmp] and (h[jm[0][i][tmp]] <= h[mid]))
        {
            tmp = jm[0][i][tmp];
        }
    }
    int ans = 0;
    if(a <= jm[0][0][tmp])
    {
        if(jm[1][0][jm[0][0][tmp]] <= d)
        {
            return 1;
        }
    }
    else
    {
        for(int i = lg; i >= 0; i--)
        {
            if(h[er[i][tmp]] <= h[mid])
            {
                ans += (1 << i);
                tmp = er[i][tmp];
            }
        }
        if(tmp == mid)
        {
            if(jm[1][0][tmp] <= d) return ans + 1;
            return -1;
        }
        if(jm[0][0][tmp] > 0 and jm[1][0][jm[0][0][tmp]] <= d)
        {
            return ans + 2;
        }
    }
    for(int i = lg; i >= 0; i--)
    {
        if(jm[1][i][tmp] < c)
        {
            ans = ans + (1 << i);
            tmp = jm[1][i][tmp];
        }
    }
    tmp = jm[1][0][tmp];
    if(c <= tmp and tmp <= d)
    {
        return ans + 1;
    }
    return -1;
}

Compilation message (stderr)

jumps.cpp:12: warning: ignoring '#pragma Gcc optimize' [-Wunknown-pragmas]
   12 | #pragma Gcc optimize("O3")
      | 
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 0; i < hh.size(); i++)
      |                    ~~^~~~~~~~~~~

• 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