Submission #966387

#	Time	Username	Problem	Language	Result	Execution time	Memory
966387		tosivanmak	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1542 ms	254880 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
struct SEG{
    vector<vector<ll> >seg;
    void init(ll n){
        seg.resize(4*n+5);
    }
    void add(ll ul, ll l, ll r, ll val, ll id){
        if(l==r){
            seg[id].pb(val);
        }
        else{
            ll mid=(l+r)>>1;
            seg[id].pb(val);
            if(ul<=mid){
            add(ul,l,mid,val,id*2);
            }
            else{
            add(ul,mid+1,r,val,id*2+1);
            }
        }
    }
    void all(ll l, ll r, ll id){
        sort(seg[id].begin(),seg[id].end());
        if(l==r){
            return;
        }
        else{
            ll mid=(l+r)>>1;
            all(l,mid,id*2),all(mid+1,r,id*2+1);
        }
    }
    ll bs(ll id, ll comp){
        if(seg[id].size()==0){
            return -1e18;
        }
        if(seg[id][0]>comp){
            return -1e18;
        }
        ll l=0,r=seg[id].size()-1;
        while(l<=r){
            if(l==r)break;
            else if(l==r-1){if(seg[id][r]<comp){l=r;}else{r=l;}}
            else{
                ll mid=(l+r)>>1;
                if(seg[id][mid]<comp){
                    l=mid;
                }
                else{
                    r=mid;
                }
            }
        }
        return seg[id][l];
    }
    ll qry(ll ql, ll qr, ll l, ll r, ll comp, ll id){
        if(ql>qr)return -1e18;
        if(l>qr||r<ql){
            return -1e18;
        }
        if(l>=ql&&r<=qr){
            return bs(id,comp);
        }
        ll mid=(l+r)>>1;
        return max(qry(ql,qr,l,mid,comp,id*2),qry(ql,qr,mid+1,r,comp,id*2+1));
    }
}mst;
struct SPARSE{
    vector<vector<pair<ll,ll> > >st;
    vector<ll>arr,lg;
    ll LOG=0;
    void init(ll n){
        st.resize(n+5);
        lg.resize(n+5);
        arr.resize(n+5);
        while((1<<LOG)<=n){
            LOG++;
        }
        for(int i=0;i<n+5;i++){
            st[i].resize(LOG+5);
        }
        lg[1]=0;
        for(int i=2;i<=n;i*=2){
            lg[i]=1;
        }
        for(int i=3;i<=n;i++){
            lg[i]+=lg[i-1];
        }
    }
    void build(ll n){
        for(int i=1;i<=n;i++){
            st[i][0]={arr[i],i};
        }
        for(int j=1;j<=LOG;j++){
            for(int i=1;i<=n;i++){
                if(i+(1<<(j-1))<=n){
                    st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    pair<ll,ll> qry(ll ql, ll qr){
        if(ql>qr)return {-1e18,-1e18};
        ll rng=lg[qr-ql+1];
        return max(st[ql][rng],st[qr-(1<<rng)+1][rng]);
    }
}st;
ll disc[200005];
ll migi[200005],hidari[200005];
ll ljmp[200005][21],sjmp[200005][21],righ[200005][21];
ll height[200005];
int n;

ll range(ll id, ll l, ll r){
    // cout<<"nigger\n"<<" "<<id<<'\n';
    if(righ[id][20]<l){
        return 3e18;
    }
    // cout<<"fuck nigger\n";
    ll ans=0;
    for(int i=20;i>=0;i--){
        if(righ[id][i]<l){
            id=righ[id][i];
            ans+=(1<<i);
        }
    }
    id=righ[id][0];
    // cout<<id<<'\n';
    ans++;
    if(id>r)return 3e18;
    return ans;
}
ll store;
ll big(ll id, ll par){
    ll ans=0;
    for(int i=20;i>=0;i--){
        if(height[ljmp[id][i]]<par){
            id=ljmp[id][i],ans+=(1<<i);
        }
    }
    store=id;
    return ans;
}
ll small(ll id, ll par){
    ll ans=0;
    for(int i=20;i>=0;i--){
        if(height[sjmp[id][i]]<par){
            id=sjmp[id][i],ans+=(1<<i);
        }
    }
    store=id;
    return ans;
}
ll specific(ll id, ll par, ll par2){
    if(par>par2){
        return 3e18;
    }
    ll one=big(id,par);
    id=store;
    if(height[ljmp[id][0]]<par2){
        return one+2;
    }
    ll bruh=small(id,par);
    return one+bruh+2;
}
void init(int N, std::vector<int> h) {
    n=N;
    st.init(n),mst.init(n);
    for(int i=0;i<n;i++){
        st.arr[i+1]=h[i];
        height[i+1]=h[i];
    }
    for(int i=0;i<n;i++){
        disc[h[i]]=i+1;
    }
    for(int i=1;i<=n;i++){
        migi[i]=-1,hidari[i]=-1;
    }
    for(int i=1;i<=n;i++){
        mst.add(i,1,n,h[i-1],1);
    }
    st.build(n);
    stack<pair<ll,ll> >stt;
    // stt.first=val, stt.second=id;
    for(int i=0;i<n;i++){
        if(stt.empty()){

        }
        else{
            while(stt.size()){
                if(stt.top().first<h[i]){
                    migi[stt.top().second]=i+1;
                    stt.pop();
                }
                else{
                    break;
                }
            }
        }
        stt.push({h[i],i+1});
    }
    while(stt.size())stt.pop();
    for(int i=n-1;i>=0;i--){
        if(stt.empty()){

        }
        else{
            while(stt.size()){
                if(stt.top().first<h[i]){
                    hidari[stt.top().second]=i+1;
                    stt.pop();
                }
                else{
                    break;
                }
            }
        }
        stt.push({h[i],i+1});
    }
    for(int i=1;i<=n;i++){
        if(migi[i]==-1){
            righ[i][0]=i;
        }
        else{
            righ[i][0]=migi[i];
        }
        if(migi[i]==-1&&hidari[i]==-1){
            ljmp[i][0]=sjmp[i][0]=i;
        }
        else{
            if(migi[i]==-1){
                ljmp[i][0]=sjmp[i][0]=hidari[i];
            }
            else if(hidari[i]==-1){
                ljmp[i][0]=sjmp[i][0]=migi[i];
            }
            else{
                if(h[hidari[i]-1]>h[migi[i]-1]){
                    ljmp[i][0]=hidari[i],sjmp[i][0]=migi[i];
                }
                else{
                    ljmp[i][0]=migi[i],sjmp[i][0]=hidari[i];
                }
            }
        }
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
          righ[i][j]=righ[righ[i][j-1]][j-1];
          ljmp[i][j]=ljmp[ljmp[i][j-1]][j-1];
          sjmp[i][j]=sjmp[sjmp[i][j-1]][j-1];
        }
    }
    // cout<<righ[14][20]<<'\n';
    mst.all(1,n,1);
}

int minimum_jumps(int a, int b, int c, int d) {
    a++,b++,c++,d++;
    pair<ll,ll>defence=st.qry(c,d);
    ll max_take=defence.first;
    pair<ll,ll>start=st.qry(a,b);
    pair<ll,ll>middle=st.qry(b+1,c-1);
    // if(middle.second>)
    if(b+1>c-1){
        if(height[b]>max_take){
            return -1;
        }
        else{
            return 1;
        }
    }
    ll ans=3e18;
    ll l=start.second+1,r=b;
    while(l<=r){
        if(l==r){
            break;
        }
        else if(l==r-1){
            if(st.qry(l,b).first<max_take){
                r=l;
            }
            else{
                l=r;
            }
        }
        else{
            ll mid=(l+r)>>1;
            if(st.qry(mid,b).first<max_take){
                r=mid;
            }
            else{
                l=mid;
            }
        }
    }
    ll lol=mst.qry(l,b,1,n,max_take,1);
    // cout<<lol<<"\n\n\n";
    if(lol!=-1e18)ans=min(ans,range(disc[lol],c,d));
    // cout<<ans<<'\n';
    if(start.first<max_take){
        ans=min(ans,specific(start.second,middle.first,max_take));
        if(start.first>middle.first){
            ans=min(ans,1LL);
        }
    }
    if(ans>=3e18){
        return -1;
    }
    return ans;
}
// 0 6 8 11
#ifdef LOCAL

int main() {
    freopen("a.out","w",stdout);
  int N, Q;
  assert(2 == scanf("%d %d", &N, &Q));
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &H[i]));
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}

#endif

• 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