Submission #1154158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154158		adhityamv	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	517 ms	43796 KiB

jumps

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
//#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
//const int INF=1000000000000000000;
const int INF=1e9;
const int N=1000000;
const int M=7+1e9;
const int ln=20;
struct Mint{   
    int n;
    Mint(int nn){
        n=nn%M;
    }
    Mint(){
        n=0;
    }
    Mint& operator+=(Mint const& m){
        n=(n+m.n)%M;
        return *this;
    }
    Mint& operator*=(Mint const& m){
        n=(n*m.n)%M;
        return *this;
    }
    Mint& operator-=(Mint const& m){
        n=(n+M-m.n)%M;
        return *this;
    }
    friend Mint binpow(Mint a,int b){
        if(b==0) return Mint(1);
        Mint r=binpow(a,b/2LL);
        r*=r;
        if(b%2==0) return r;
        r*=a;
        return r;
    }
    friend Mint inverse(Mint a){
        return binpow(a,M-2);
    }
    Mint& operator/=(Mint const &b){
        return (*this)*=inverse(b);
    }
    friend Mint operator+(Mint a,Mint const b){
        return (a+=b);
    }
    friend Mint operator-(Mint a,Mint const b){
        return (a-=b);
    }
    friend Mint operator*(Mint a,Mint const b){
        return (a*=b);
    }
    friend Mint operator/(Mint a,Mint const b){
        return (a/=b);
    }
    friend Mint operator-(Mint a){
        return 0-a;
    }
    friend std::ostream& operator<<(std::ostream& os, Mint const& a){
        return os << a.n;
    }
    friend std::istream& operator>>(std::istream& is, Mint& a){
        return (is >> a.n);
    }
    friend bool operator==(Mint const& a,Mint const& b){
        return a.n==b.n;
    }
    friend bool operator!=(Mint const& a,Mint const& b){
        return a.n!=b.n;
    }
};
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << " " << p.se << "\n";
}
int n;
vector<int> h;
vector<int> big[ln];
vector<int> sm[ln];
vector<int> fr;
vector<int> fl;
int seg[2*N];
vector<int> invh;
void build(){
    for(int i=n;i<2*n;i++){
        seg[i]=h[i-n];
    }
    for(int i=n-1;i>=1;i--){
        seg[i]=max(seg[2*i],seg[2*i+1]);
    }
}
int query(int l,int r){
    l+=n;
    r+=n;
    int ans=-1;
    while(l<r){
        if(l&1) ans=max(ans,seg[l++]);
        if(r&1) ans=max(ans,seg[--r]);
        l>>=1;
        r>>=1;
    }
    return ans;
}
int queryrm(int l,int r,int val){
    if(r==l+1){
        if(h[l]>=val) return l;
        return -1;
    }
    int m=(l+r)/2;
    if(query(m,r)>=val){
        return queryrm(m,r,val);
    } else return queryrm(l,m,val);
}
void getfr(){
    stack<int> s;
    s.push(n);
    for(int i=n-1;i>=0;i--){
        while(s.top()!=n && h[s.top()]<h[i]){
            s.pop();
        }
        fr[i]=s.top();
        s.push(i);
    }
}
void getfl(){
    stack<int> s;
    s.push(n);
    for(int i=0;i<n;i++){
        while(s.top()!=n && h[s.top()]<h[i]){
            s.pop();
        }
        fl[i]=s.top();
        s.push(i);
    }
}
void init(int nn,vector<int> hh){
    n=nn;
    h=hh;
    for(int i=0;i<n+1;i++) invh.push_back(0);
    for(int i=0;i<n;i++) invh[h[i]]=i;
    h.push_back(INF);
    for(int i=0;i<n;i++){
        fr.push_back(n);
        fl.push_back(-1);
    }
    getfr();
    getfl();
    for(int i=0;i<ln;i++){
        for(int j=0;j<n+1;j++){
            big[i].push_back(n);
            sm[i].push_back(n);
        }
    }
    for(int i=0;i<n;i++){
        if(h[fl[i]]>h[fr[i]]){
            big[0][i]=fl[i];
            sm[0][i]=fr[i];
        } else{
            big[0][i]=fr[i];
            sm[0][i]=fl[i];
        }
    }
    big[0][n]=n;
    sm[0][n]=n;
    for(int j=1;j<ln;j++){
        for(int i=0;i<n;i++){
            sm[j][i]=sm[j-1][sm[j-1][i]];
            big[j][i]=big[j-1][big[j-1][i]];
        }
    }
    build();
}
int minimum_jumps(int a,int b,int c,int d){
    int mx=query(c,d+1);
    int t=query(b+1,c);
    int rmind=queryrm(a,b+1,t);
    if(rmind!=-1){
        if(fr[rmind]<=d) return 1;
    }
    if(rmind==b){
        return -1;
    }
    int ind;
    if(rmind==-1){
        ind=invh[query(a,b+1)];
    } else ind=invh[query(rmind+1,b+1)];
    int fans=0;
    for(int j=ln-1;j>=0;j--){
        if(h[big[j][ind]]<t){
            ind=big[j][ind];
            fans+=(1<<j);
        }
    }
    if(h[big[0][ind]]<mx) return fans+2;
    for(int j=ln-1;j>=0;j--){
        if(h[sm[j][ind]]<=mx && sm[j][ind]<c){
            ind=sm[j][ind];
            fans+=(1<<j);
        }
    }
    if(sm[0][ind]<=d && sm[0][ind]>=c) return fans+1;
    return -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