Submission #725725

#	Time	Username	Problem	Language	Result	Execution time	Memory
725725		n0sk1ll	Rainforest Jumps (APIO21_jumps)	C++14	56 / 100	4073 ms	89544 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

const int N=5'000'006;
int val[N],L[N],R[N];
int idx=0;

void add(int p, int q, int l, int r, int s, int x)
{
    val[p]+=x;
    if (l==r) return;
    int mid=(l+r)/2;
    if (s<=mid) L[p]=++idx,R[p]=R[q],add(L[p],L[q],l,mid,s,x);
    else L[p]=L[q],R[p]=++idx,add(R[p],R[q],mid+1,r,s,x);
}

int WalkLower(int p, int q, int l, int r, int x)
{
    if (l>x) return -1;
    if (val[p]-val[q]==0) return -1;
    if (l==r) return r;
    int mid=(l+r)/2;
    int mozda=WalkLower(R[p],R[q],mid+1,r,x);
    if (mozda==-1) return WalkLower(L[p],L[q],l,mid,x);
    return mozda;
}

int WalkUpper(int p, int q, int l, int r, int x)
{
    if (r<x) return -1;
    if (val[p]-val[q]==0) return -1;
    if (l==r) return r;
    int mid=(l+r)/2;
    int mozda=WalkUpper(L[p],L[q],l,mid,x);
    if (mozda==-1) return WalkUpper(R[p],R[q],mid+1,r,x);
    return mozda;
}

int svakislucaj[69]; //pomaze pri definiciji root[-1]...
int root[200005]; //root za svakog xd;

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);

    root[-1]=0;
    ff(i,0,n) root[i]=++idx,add(root[i],root[i-1],1,n,h[i],1);

    /*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)
{
    int bridge=ST.Max(1,B+1,C-1);
    int mali=WalkLower(root[B],root[A-1],1,n,bridge);
    int veliki=WalkUpper(root[B],root[A-1],1,n,bridge);
    int ogromni=gde[ST.Max(1,A,B)];
    int plafon=ST.Max(1,C,D);

    if (bridge<0) mali=ST.Min(1,A,B),veliki=mali;

    if (mali==-1) mali=ogromni;
    else mali=gde[mali];
    if (veliki==-1) veliki=ogromni;
    else veliki=gde[veliki];

    int pmali=putuj(mali,C,D,plafon);
    int pveliki=putuj(veliki,C,D,plafon);
    int pogromni=putuj(ogromni,C,D,plafon);

    int ans=mod;
    ans=min(ans,pmali);
    ans=min(ans,pveliki);
    ans=min(ans,pogromni);
    
    fff(i,A,B) ans=min(ans,putuj(i,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

*/

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:157:12: warning: array subscript -1 is below array bounds of 'int [200005]' [-Warray-bounds]
  157 |     root[-1]=0;
      |     ~~~~~~~^

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