oj.uz

Submission #587705

# Submission time Handle Problem Language Result Execution time Memory
587705 2022-07-02T08:57:09 Z krit3379 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 2379 ms 20424 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=0;
        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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 898 ms 16764 KB Output is correct
4 Correct 2379 ms 20356 KB Output is correct
5 Correct 1565 ms 10448 KB Output is correct
6 Correct 2270 ms 20352 KB Output is correct
7 Correct 1729 ms 14732 KB Output is correct
8 Correct 2318 ms 20412 KB Output is correct

Subtask #2
0 / 8.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 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 0 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 0 ms 336 KB Output is correct
5 Correct 815 ms 16928 KB Output is correct
6 Correct 1031 ms 20356 KB Output is correct
7 Correct 471 ms 10636 KB Output is correct
8 Correct 1057 ms 20356 KB Output is correct
9 Correct 114 ms 3260 KB Output is correct
10 Correct 1027 ms 20356 KB Output is correct
11 Correct 987 ms 20352 KB Output is correct
12 Incorrect 1016 ms 20424 KB Output isn't correct
13 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 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 652 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 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 652 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 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 898 ms 16764 KB Output is correct
4 Correct 2379 ms 20356 KB Output is correct
5 Correct 1565 ms 10448 KB Output is correct
6 Correct 2270 ms 20352 KB Output is correct
7 Correct 1729 ms 14732 KB Output is correct
8 Correct 2318 ms 20412 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Incorrect 2 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -