oj.uz

Submission #587702

# Submission time Handle Problem Language Result Execution time Memory
587702 2022-07-02T08:53:09 Z krit3379 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 931 ms 16800 KB 
#include<bits/stdc++.h>
#include "jumps.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 200005

int t[4*N],arr[N],nxt[20][N],n;

void cre(int x,int l,int r){
    if(l==r){t[x]=arr[l];return ;}
    int mid=(l+r)/2;
    cre(x*2,l,mid);
    cre(x*2+1,mid+1,r);
    t[x]=max(t[x*2],t[x*2+1]);
}

int sol(int x,int l,int r,int ll,int rr){
    if(l>rr||ll>r||ll>rr)return 0;
    if(ll<=l&&r<=rr)return t[x];
    int mid=(l+r)/2;
    return max(sol(x*2,l,mid,ll,rr),sol(x*2+1,mid+1,r,ll,rr));
}

void init(int nn,vector<int> h){
    int i,j,l,r,mid,val;
    n=nn;
    for(i=0;i<n;i++)arr[i+1]=h[i];
    cre(1,1,n);
    for(i=0;i<20;i++)for(j=0;j<=n+1;j++)nxt[i][j]=n+1;
    for(i=1;i<=n;i++){
        l=i+1,r=n;
        while(l<=r){
            mid=(l+r)/2;
            if(sol(1,1,n,i+1,mid)>arr[i])nxt[0][arr[i]]=arr[mid],r=mid-1;
            else l=mid+1;
        }
        val=n+1;
        l=1,r=i-1;
        while(l<=r){
            mid=(l+r)/2;
            if(sol(1,1,n,mid,i-1)>arr[i])val=arr[mid],l=mid+1;
            else r=mid-1;
        }
        nxt[0][arr[i]]=max(nxt[0][arr[i]],val);
    }
    for(i=1;i<20;i++)for(j=1;j<=n;j++)nxt[i][j]=nxt[i-1][nxt[i-1][j]];
    return ;
}

int minimum_jumps(int a,int b,int c,int d){
    a++,b++,c++,d++;
    int i,ml,mm,mr,pos,now,l,r,mid,v,val,ans;
    ml=sol(1,1,n,a,b);
    mm=sol(1,1,n,b+1,c-1);
    mr=sol(1,1,n,c,d);
    if(mm>mr)return -1;
    if(ml<mm){
        now=ml;
        ans=1;
        l=c,r=d;
        while(l<=r){
            mid=(l+r)/2;
            if(sol(1,1,n,c,mid)>mm)pos=mid,r=mid-1;
            else l=mid+1;
        }
        for(i=19;i>=0;i--)if(nxt[i][now]<arr[pos])ans+=1<<i,now=nxt[i][now];
        return ans;
    }
    pos=-1;
    l=a,r=b;
    while(l<=r){
        mid=(l+r)/2;
        if(sol(1,1,n,mid,b)>mm)pos=mid,l=mid+1;
        else r=mid-1;
    }
    if(pos!=-1&&arr[pos]<mr)return 1;
    pos=-1;
    l=a,r=b;
    while(l<=r){
        mid=(l+r)/2;
        v=sol(1,1,n,mid,b);
        if(v<mm)pos=mid,val=v,r=mid-1;
        else l=mid+1;
    }
    if(pos==-1||val>mr)return -1;
    pos=-1;
    l=a,r=b;
    while(l<=r){
        mid=(l+r)/2;
        if(sol(1,1,n,mid,b)<=val)pos=mid,l=mid+1;
        else r=mid-1;
    }
    now=arr[pos];
    ans=1;
        l=c,r=d;
    while(l<=r){
        mid=(l+r)/2;
        if(sol(1,1,n,c,mid)>mm)pos=mid,r=mid-1;
        else l=mid+1;
    }
    for(i=19;i>=0;i--)if(nxt[i][now]<arr[pos])ans+=1<<i,now=nxt[i][now];
    return ans;
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:86:20: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     if(pos==-1||val>mr)return -1;
      |                 ~~~^~~
jumps.cpp:67:49: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |         for(i=19;i>=0;i--)if(nxt[i][now]<arr[pos])ans+=1<<i,now=nxt[i][now];
      |                                          ~~~~~~~^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 931 ms 16768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Incorrect 851 ms 16800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 684 ms 9652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 684 ms 9652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Incorrect 931 ms 16768 KB Output isn't correct
4 Halted 0 ms 0 KB -