Submission #734171

#	Time	Username	Problem	Language	Result	Execution time	Memory
734171		bin9638	Rainforest Jumps (APIO21_jumps)	C++17	8 / 100	4070 ms	79388 KiB

jumps

#include <bits/stdc++.h>

#ifndef SKY
#include "jumps.h"
#endif // SKY

using namespace std;

#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

struct IT
{
    int ST[N*4];

    void init()
    {
        memset(ST,-0x3f3f,sizeof(ST));
    }

    void update(int id,int l,int r,int i,int val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id]=val;
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id]=max(ST[id*2],ST[id*2+1]);
    }

    int get(int id,int l,int r,int u,int v)
    {
        if(u>v||l>v||r<u)
            return -1e9;
        if(l>=u&&r<=v)
            return ST[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
}IT;

int n,h[N],pos[N],truoc[N][21],sau[N][21],LOG,dis[210][210];

void init(int NNN, vector<int> HHH)
{
    n=NNN;
    for(int i=0;i<n;i++)
        h[i+1]=HHH[i],pos[HHH[i]]=i+1;
    LOG=log2(n);
    IT.init();
    for(int i=n;i>=1;i--)
    {
        if(IT.get(1,1,n,1,pos[i]-1)>=-n)
            truoc[pos[i]][0]=abs(IT.get(1,1,n,1,pos[i]-1));
        IT.update(1,1,n,pos[i],pos[i]);
    }
    IT.init();
    for(int i=n;i>=1;i--)
    {
        if(IT.get(1,1,n,pos[i]+1,n)>=-n)
            sau[pos[i]][0]=abs(IT.get(1,1,n,pos[i]+1,n));
        IT.update(1,1,n,pos[i],-pos[i]);
    }
    for(int k=1;k<=LOG;k++)
        for(int i=1;i<=n;i++)
            {
                sau[i][k]=sau[sau[i][k-1]][k-1];
                truoc[i][k]=truoc[truoc[i][k-1]][k-1];
            }
   // for(int i=1;i<=n;i++)cout<<truoc[i][0]<<" "<<sau[i][0]<<endl;
    IT.init();
    for(int i=1;i<=n;i++)
        IT.update(1,1,n,i,h[i]);
    memset(dis,0x3f3f,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        if(truoc[i][0]!=0)
            dis[i][truoc[i][0]]=1;
        if(sau[i][0]!=0)
            dis[i][sau[i][0]]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}

int solve(int vt,int C,int D)
{
    int res=0;
    for(int k=LOG;k>=0;k--)
        if(sau[vt][k]!=0&&sau[vt][k]<C)
        {
            res+=(1<<k);
            vt=sau[vt][k];
        }
    vt=sau[vt][0];
    res++;
    if(vt>=C&&vt<=D)
        return res;
    return 1e9;
}

int minimum_jumps(int A, int B, int C, int D)
{
    A++;B++;C++;D++;
    //if(IT.get(1,1,n,B,C-1)>IT.get(1,1,n,C,D))
      //  return -1;
  /*  int l=A,r=B,vt;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(IT.get(1,1,n,mid,B)<IT.get(1,1,n,C,D))
        {
            vt=mid;
            r=mid-1;
        }else
        {
            l=mid+1;
        }
    }
    int val=IT.get(1,1,n,vt,B);
    l=A,r=B;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(IT.get(1,1,n,mid,B)>=val)
        {
            vt=mid;
            l=mid+1;
        }else
            r=mid-1;
    }
    int res=solve(vt,C,D),dem=0;
    while(truoc[vt][0]!=0)
    {
        vt=truoc[vt][0];
        dem++;
        res=min(res,solve(vt,C,D)+dem);
    }
    for(int i=A;i<=B;i++)
        res=min(res,solve(i,C,D));
    if(res>n)
        return -1;*/
    int res=1e9;
    for(int i=A;i<=B;i++)
        for(int j=C;j<=D;j++)
            res=min(res,dis[i][j]);
    return (res>n ? -1 :res);
}


#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<int>H(n);
    for(int i=0;i<n;i++)
        cin>>H[i];
    init(n,H);
    int q;
    cin>>q;
    while(q--)
    {
        int A,B,C,D;
        cin>>A>>B>>C>>D;
        cout<<minimum_jumps(A,B,C,D)<<endl;
    }
    return 0;
}
#endif

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