제출 #734186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734186		bin9638	밀림 점프 (APIO21_jumps)	C++17	100 / 100	2733 ms	56016 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,nxt[N][21];

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]);
    for(int i=1;i<=n;i++)
        if(h[truoc[i][0]]>h[sau[i][0]])
            nxt[i][0]=truoc[i][0];
                else nxt[i][0]=sau[i][0];
    for(int k=1;k<=LOG;k++)
        for(int i=1;i<=n;i++)
            nxt[i][k]=nxt[nxt[i][k-1]][k-1];
}

bool check(int vt,int C,int D)
{
    return(vt>=C&&vt<=D);
}

int get_next(int vt,int k)
{
    //cout<<vt<<" "<<k<<endl;
    for(int i=0;i<k;i++)
        vt=nxt[vt][i];
    return vt;
}

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=0;
    val=IT.get(1,1,n,C,D);
   // cout<<get_next(3,1)<<" "<<nxt[3][0]<<endl;return 0;
    for(int k=LOG;k>=0;k--)
        if(nxt[vt][k]!=0&&sau[get_next(vt,k)][0]!=0&&sau[get_next(vt,k)][0]<C&&h[nxt[vt][k]]<val)
        {
         //   cout<<vt<<" "<<k<<" "<<get_next(vt,k)<<endl;
            vt=nxt[vt][k];
            res+=(1<<k);
        }
    for(int k=LOG;k>=0;k--)
        if(sau[vt][k]!=0&&sau[vt][k]<C)
            vt=sau[vt][k],res+=(1<<k);
    return res+1;
}


#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

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:110:17: warning: 'vt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |     int l=A,r=B,vt;
      |                 ^~

• 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