Submission #618025

#	Time	Username	Problem	Language	Result	Execution time	Memory
618025		MohamedAliSaidane	Rainforest Jumps (APIO21_jumps)	C++14	33 / 100	4085 ms	46476 KiB

jumps

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "jumps.h"
        using namespace __gnu_pbds;
        using namespace std;

        typedef tree<int,null_type,less<int>,rb_tree_tag,
        tree_order_statistics_node_update> indexed_set;

        typedef long long ll;
        typedef long double ld;

        //#define int ll

        typedef pair<int,int> pii;
        typedef pair<ll,ll> pll;
        typedef pair<ld,ld> pld;

        typedef vector<int> vi;
        typedef vector<ll> vll;
        typedef vector<pii> vpi;
        typedef vector<pll> vpl;

        #define pb push_back
        #define popb pop_back
        #define pp pop_back
        #define pf push_front
        #define popf pop_front
        #define all(x) (x).begin(),(x).end()
        #define ff first
        #define ss second



        int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
        ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
        ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}


        const ll MOD =   998244353;

        int n;
        vll A;
        const int nax = 2e5 + 4;
        ll sp[nax][20];
        int LG[nax];
        int L[nax], R[nax];
        void build()
        {
            for(int i = 0; i < n; i++)
                sp[i][0] = A[i];
            for(int j = 1; j < 20; j++)
                for(int i=  0; i + (1 << j) <= n; i ++)
                    sp[i][j] = max(sp[i][j-1],sp[i + (1 << (j-1))][j - 1]);
        }
        int rmq(int l, int r)
        {
            int j = LG[r - l + 1];
            return max(sp[l][j], sp[r - (1 << j) + 1][j]);
        }
        void init(int N, vi H)
        {
            n = N;
            for(int i = 0 ; i < n;i ++)
                A.pb(H[i]);
            LG[1] = 0;
            for(int i =2; i < nax;i ++)
                LG[i] = LG[i/2] + 1;
            build();
            memset(L, -1, sizeof(L));
            memset(R, -1, sizeof(R));
            for(int i = 0 ;i  < n; i++)
            {
                int debut = 0;
                int fin =i -1;
                int rep = -1;
                while(debut <= fin)
                {
                    int mid = (debut + fin)/2;
                    if(rmq(mid, i) > A[i])
                    {
                        rep = mid;
                        debut = mid + 1;
                    }
                    else
                        fin =mid - 1;
                }
                L[i] = rep;
                debut =i + 1;
                fin = n- 1;
                rep = -1;
                while(debut <= fin)
                {
                    int mid = ( debut + fin  )/2;
                    if(rmq(i, mid) > A[i])
                    {
                        rep = mid ;
                        fin = mid - 1;
                    }
                    else
                        debut = mid + 1;
                }
                R[i] = rep;
            }
        }
        int minimum_jumps(int a, int b, int c, int d)
        {
            set<pii> pq;
            for(int i = a; i <= b;i ++)
                pq.insert({0, i});
            int sp[n];
            for(int i=  0 ; i < n; i++)
                sp[i] = MOD;
            while(!pq.empty())
            {
                pii u = *(pq.begin());
                pq.erase(pq.begin());
                int dis = u.ff;
                int node =u.ss;
                if(node >= c && node <= d)
                    return dis;
                if(dis > sp[node])
                    continue;
                int nxt;
                if(L[node] == -1)
                    nxt = R[node];
                else
                {
                    if(R[node] == -1)
                        nxt = L[node];
                    else
                    {
                        if(L[node] >= c && L[node] <= d)
                            nxt = L[node];
                        else if(R[node] >= c && R[node] <= d)
                        {
                            nxt = R[node];
                        }
                        else
                        {
                            if(A[L[node]] >= A[R[node]])
                            {
                                if(A[L[node]] >= rmq(c, d))
                                    nxt = R[node];
                                else
                                    nxt = L[node];
                            }
                            else
                            {
                                if(A[R[node]] >= rmq(c,d))
                                    nxt = L[node];
                                else
                                    nxt = R[node];
                            }
                        }
                    }
                }
                if(nxt != -1 && sp[nxt] > dis + 1)
                {
                    pq.insert({dis + 1, nxt});
                    sp[nxt] = dis + 1;
                }
            }
            return -1;
        }

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