oj.uz

Submission #734101

# Submission time Handle Problem Language Result Execution time Memory
734101 2023-05-01T16:45:30 Z bin9638 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 2131 ms 39512 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);
    }
    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 350 ms 32060 KB Output is correct
4 Correct 2017 ms 39336 KB Output is correct
5 Correct 1734 ms 21676 KB Output is correct
6 Correct 1828 ms 39432 KB Output is correct
7 Correct 1649 ms 27944 KB Output is correct
8 Correct 2131 ms 39436 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 3 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

# 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 3 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

# Verdict Execution time Memory Grader output
1 Correct 3 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 220 ms 32416 KB Output is correct
6 Correct 259 ms 39512 KB Output is correct
7 Correct 147 ms 21876 KB Output is correct
8 Correct 254 ms 39484 KB Output is correct
9 Correct 28 ms 8872 KB Output is correct
10 Correct 283 ms 39332 KB Output is correct
11 Correct 172 ms 39432 KB Output is correct
12 Correct 174 ms 39348 KB Output is correct
13 Correct 177 ms 39428 KB Output is correct
14 Correct 248 ms 39444 KB Output is correct
15 Incorrect 189 ms 39432 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 19816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 19816 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 350 ms 32060 KB Output is correct
4 Correct 2017 ms 39336 KB Output is correct
5 Correct 1734 ms 21676 KB Output is correct
6 Correct 1828 ms 39432 KB Output is correct
7 Correct 1649 ms 27944 KB Output is correct
8 Correct 2131 ms 39436 KB Output is correct
9 Correct 2 ms 3408 KB Output is correct
10 Correct 2 ms 3408 KB Output is correct
11 Correct 3 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 -