oj.uz

Submission #734105

# Submission time Handle Problem Language Result Execution time Memory
734105 2023-05-01T16:50:11 Z bin9638 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1993 ms 39508 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 323 ms 32040 KB Output is correct
4 Correct 1839 ms 39476 KB Output is correct
5 Correct 1364 ms 21444 KB Output is correct
6 Correct 1729 ms 39368 KB Output is correct
7 Correct 1442 ms 27964 KB Output is correct
8 Correct 1993 ms 39368 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory 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 4 ms 3408 KB Output is correct
6 Correct 4 ms 3408 KB Output is correct
7 Correct 3 ms 3408 KB Output is correct
8 Incorrect 4 ms 3408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory 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 4 ms 3408 KB Output is correct
6 Correct 4 ms 3408 KB Output is correct
7 Correct 3 ms 3408 KB Output is correct
8 Incorrect 4 ms 3408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory 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 209 ms 32380 KB Output is correct
6 Correct 245 ms 39384 KB Output is correct
7 Correct 123 ms 21904 KB Output is correct
8 Correct 256 ms 39508 KB Output is correct
9 Correct 27 ms 8836 KB Output is correct
10 Correct 254 ms 39372 KB Output is correct
11 Correct 170 ms 39432 KB Output is correct
12 Correct 175 ms 39336 KB Output is correct
13 Correct 176 ms 39476 KB Output is correct
14 Correct 244 ms 39436 KB Output is correct
15 Incorrect 197 ms 39368 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory 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 358 ms 19912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory 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 358 ms 19912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 323 ms 32040 KB Output is correct
4 Correct 1839 ms 39476 KB Output is correct
5 Correct 1364 ms 21444 KB Output is correct
6 Correct 1729 ms 39368 KB Output is correct
7 Correct 1442 ms 27964 KB Output is correct
8 Correct 1993 ms 39368 KB Output is correct
9 Correct 2 ms 3408 KB Output is correct
10 Correct 2 ms 3408 KB Output is correct
11 Correct 2 ms 3408 KB Output is correct
12 Correct 2 ms 3408 KB Output is correct
13 Correct 4 ms 3408 KB Output is correct
14 Correct 4 ms 3408 KB Output is correct
15 Correct 3 ms 3408 KB Output is correct
16 Incorrect 4 ms 3408 KB Output isn't correct
17 Halted 0 ms 0 KB -