oj.uz

답안 #734103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734103 2023-05-01T16:46:50 Z bin9638 밀림 점프 (APIO21_jumps) C++17
4 / 100
 2282 ms 39480 KB 
#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;

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

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);
    }
    if(res>n)
        return -1;
    return 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

Compilation message

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

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 337 ms 32104 KB Output is correct
4 Correct 2020 ms 39436 KB Output is correct
5 Correct 1740 ms 21532 KB Output is correct
6 Correct 2282 ms 39368 KB Output is correct
7 Correct 1141 ms 27972 KB Output is correct
8 Correct 2129 ms 39324 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Incorrect 4 ms 3408 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Incorrect 4 ms 3408 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 223 ms 32384 KB Output is correct
6 Correct 276 ms 39436 KB Output is correct
7 Correct 138 ms 21888 KB Output is correct
8 Correct 282 ms 39384 KB Output is correct
9 Correct 29 ms 8784 KB Output is correct
10 Correct 280 ms 39480 KB Output is correct
11 Correct 182 ms 39348 KB Output is correct
12 Correct 172 ms 39336 KB Output is correct
13 Correct 176 ms 39436 KB Output is correct
14 Correct 221 ms 39388 KB Output is correct
15 Incorrect 191 ms 39336 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Incorrect 342 ms 19912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Incorrect 342 ms 19912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 337 ms 32104 KB Output is correct
4 Correct 2020 ms 39436 KB Output is correct
5 Correct 1740 ms 21532 KB Output is correct
6 Correct 2282 ms 39368 KB Output is correct
7 Correct 1141 ms 27972 KB Output is correct
8 Correct 2129 ms 39324 KB Output is correct
9 Correct 2 ms 3408 KB Output is correct
10 Correct 2 ms 3456 KB Output is correct
11 Correct 2 ms 3408 KB Output is correct
12 Correct 2 ms 3408 KB Output is correct
13 Incorrect 4 ms 3408 KB Output isn't correct
14 Halted 0 ms 0 KB -