Submission #725743

#	Time	Username	Problem	Language	Result	Execution time	Memory
725743		n0sk1ll	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	2523 ms	44924 KiB

jumps

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#include "jumps.h"

struct segtree
{
    int k=1;
    int mn[550001],mx[550001];
    int l[550001],r[550001];

    void Build(vector<int> &niz, int n)
    {
        while (k<n) k*=2;
        ff(i,0,k) l[i+k]=i,r[i+k]=i;
        bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
        ff(i,0,n) mn[i+k]=niz[i],mx[i+k]=niz[i];
        bff(i,1,k) mn[i]=min(mn[2*i],mn[2*i+1]);
        bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);
    }

    int Min(int p, int ll, int rr)
    {
        if (ll>r[p] || rr<l[p]) return mod;
        if (ll<=l[p] && rr>=r[p]) return mn[p];
        return min(Min(2*p,ll,rr),Min(2*p+1,ll,rr));
    }

    int Max(int p, int ll, int rr)
    {
        if (ll>r[p] || rr<l[p]) return -mod;
        if (ll<=l[p] && rr>=r[p]) return mx[p];
        return max(Max(2*p,ll,rr),Max(2*p+1,ll,rr));
    }

} ST;

int h[200005],gde[200005];
int levo[200005],desno[200005];
int opt[20][200005]; //jumping jacks
int grb[20][200005]; //naivno teranje udesno

int n;
void init(int N, vector<int> H)
{
    n=N;

    ff(i,0,n) h[i]=H[i],gde[h[i]]=i;

    stack<int> mono;
    ff(i,0,n)
    {
        while (!mono.empty() && h[mono.top()]<h[i]) mono.pop();
        if (mono.empty()) levo[i]=-1; else levo[i]=mono.top();
        mono.push(i);
    }
    while (!mono.empty()) mono.pop();
    bff(i,0,n)
    {
        while (!mono.empty() && h[mono.top()]<h[i]) mono.pop();
        if (mono.empty()) desno[i]=-1; else desno[i]=mono.top();
        mono.push(i);
    }

    ff(i,0,n)
    {
        if (levo[i]==-1) opt[0][i]=desno[i];
        else if (desno[i]==-1) opt[0][i]=levo[i];
        else opt[0][i]=(h[levo[i]]>h[desno[i]]?levo[i]:desno[i]);
    }

    ff(k,1,20) ff(i,0,n)
    {
        if (opt[k-1][i]==-1) opt[k][i]=-1;
        else opt[k][i]=opt[k-1][opt[k-1][i]];
    }

    ff(i,0,n) grb[0][i]=desno[i];
    ff(k,1,20) ff(i,0,n)
    {
        if (grb[k-1][i]==-1) grb[k][i]=-1;
        else grb[k][i]=grb[k-1][grb[k-1][i]];
    }

    ST.Build(H,n);

    /*ff(i,0,n) cout<<levo[i]<<" "; cout<<endl;
    ff(i,0,n) cout<<desno[i]<<" "; cout<<endl;
    cout<<endl;*/

    /*ff(k,0,20)
    {
        ff(i,0,n) cout<<opt[k][i]<<" ";
        cout<<endl;
    } cout<<endl;*/

    /*ff(k,0,20)
    {
        ff(i,0,n) cout<<grb[k][i]<<" ";
        cout<<endl;
    } cout<<endl;*/
}

bool presisao(int ko, int C, int D, int plafon)
{
    if (ko==-1) return true;
    if (h[ko]>plafon) return true;
    if (ko>=C) return true;
    if (desno[ko]>=C) return true;
    return false;
}

bool staje(int ko, int C, int D)
{
    return C<=ko && ko<=D;
}

int putuj(int ko, int C, int D, int plafon)
{
    int skokovi=0;
    bff(k,0,20) if (!presisao(opt[k][ko],C,D,plafon)) ko=opt[k][ko],skokovi+=(1<<k);

    if (staje(ko,C,D)) return skokovi;
    if (staje(desno[ko],C,D)) return skokovi+1;
    if (desno[ko]!=-1 && staje(desno[desno[ko]],C,D)) return skokovi+2;
    if (levo[ko]!=-1 && staje(desno[levo[ko]],C,D)) return skokovi+2;

    while (levo[ko]!=-1 && h[levo[ko]]<plafon) ko=levo[ko],skokovi++; ///ne bi trebalo da pogorsa slozenost...
    bff(k,0,20) if (grb[k][ko]!=-1 && grb[k][ko]<C) ko=grb[k][ko],skokovi+=(1<<k);
    if (!staje(ko,C,D)) ko=grb[0][ko],skokovi++;
    if (staje(ko,C,D)) return skokovi;

    return mod;
}

int minimum_jumps(int A, int B, int C, int D)
{
    vector<int> putnici;
    int plafon=ST.Max(1,C,D);
    int bridge=ST.Max(1,B+1,C-1);

    int l=A-1,r=B+1;
    while (r-l>1)
    {
        int mid=(l+r)/2;
        if (ST.Max(1,mid,B)<bridge) r=mid;
        else l=mid;
    }

    if (l>=A) putnici.pb(l);
    if (r<=B)
    {
        int sta=ST.Max(1,r,B);
        l=r,r=B+1;
        while (r-l>1)
        {
            int mid=(l+r)/2;
            if (ST.Max(1,mid,B)==sta) l=mid;
            else r=mid;
        }
        putnici.pb(l);
    }

    int ans=mod;
    for (auto p : putnici) ans=min(ans,putuj(p,C,D,plafon));

    if (ans>n) ans=-1;
    return ans;
}

/*

5 1000
1 2 3 4 5
0 0 4 4

7 1000
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2

10 1000
9 1 2 3 4 5 6 7 8 10
0 0 1 1
1 1 5 5
1 1 6 6

*/

• 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