oj.uz

Submission #415225

# Submission time Handle Problem Language Result Execution time Memory
415225 2021-05-31T17:22:43 Z A_D Rainforest Jumps (APIO21_jumps) C++14
23 / 100
 3342 ms 44108 KB 
#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;
const int NN=2e5+100;
const int L=18;
const int INF=1e9;
int a[NN];
bool vis[NN];
int seg[4*NN];
int n;
vector<int> g[NN];
vector<int> vec;
int st[NN][L][2];
void build(int p,int s,int e)
{
	if(s==e){
		seg[p]=a[s];
		return;
	}
	int mid=(s+e)/2;
	build(2*p,s,mid);
	build(2*p+1,mid+1,e);
	seg[p]=max( seg[2*p],seg[2*p+1]);
}

int get(int p,int s,int e,int a, int b)
{
    if(a<=s&&e<=b){
		return seg[p];
    }
	if(s>b||e<a){
		return 0;
	}
	int mid=(s+e)/2;
	return max(get(2*p,s,mid,a,b),get(2*p+1,mid+1,e,a,b));
}

void init(int N, std::vector<int> H) {
    n=N;
    for(int i=0;i<L;i++){
        st[n+1][i][0]=n+1;
        st[n+1][i][1]=n+1;
    }
    for(int i=0;i<N;i++){
        a[i]=H[i];
    }
    build(1,0,n-1);
    for(int i=0;i<n;i++){
        if(i!=n-1&&get(1,0,n-1,i,n-1)!=a[i]){
            int ans,l=i,r=n-1;
            while(l<=r){
                int mid=(l+r)/2;
                int v=get(1,0,n-1,i+1,mid);
                if(v>=a[i]){
                    ans=mid;
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
            g[a[i]].push_back(a[ans]);
        }
        if(i!=0&&get(1,0,n-1,0,i)!=a[i]){
            int ans,l=0,r=i;
            while(l<=r){
                int mid=(l+r)/2;
                int v=get(1,0,n-1,mid,i-1);
                if(v>=a[i]){
                    ans=mid;
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
            g[a[i]].push_back(a[ans]);
        }
        sort(g[a[i]].begin(),g[a[i]].end());
        if(g[a[i]].size()>0){
            st[a[i]][0][0]=g[a[i]][0];
        }
        else{
            st[a[i]][0][0]=n+1;
        }
        if(g[a[i]].size()>1){
            st[a[i]][0][1]=g[a[i]][1];
        }
        else{
            st[a[i]][0][1]=n+1;
        }
    }
    for(int j=1;j<L;j++){
        for(int i=1;i<=n;i++){
            int r=i;
            r=st[r][j-1][0];
            r=st[r][j-1][0];
            st[i][j][0]=r;
            r=i;
            r=st[r][j-1][1];
            r=st[r][j-1][1];
            st[i][j][1]=r;
        }
    }
}
int dfs(int u,int tar)
{
    int ret=0;
    for(int i=1;i>=0;i--){
        for(int j=L-1;j>=0;j--){
            int r=st[u][j][i];
            if(r<=tar){
                ret+=(1<<j);
                u=r;
            }
        }
    }
    if(u==tar)return ret;
    else return INF;
}
int minimum_jumps(int A, int B, int C, int D) {
    int u=a[A];
    int tar=a[C];
    
    int ans=dfs(u,tar);
    if(ans==INF)ans=-1;
    return ans;
}

Compilation message

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:52:17: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |             int ans,l=i,r=n-1;
      |                 ^~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 4 ms 4936 KB Output is correct
4 Correct 1087 ms 22788 KB Output is correct
5 Correct 2994 ms 43816 KB Output is correct
6 Correct 851 ms 11456 KB Output is correct
7 Correct 3095 ms 43808 KB Output is correct
8 Correct 1162 ms 18704 KB Output is correct
9 Correct 3125 ms 43864 KB Output is correct
10 Correct 2040 ms 43804 KB Output is correct
11 Correct 3298 ms 44108 KB Output is correct
12 Correct 2452 ms 43808 KB Output is correct
13 Correct 3139 ms 44028 KB Output is correct
14 Correct 3342 ms 43756 KB Output is correct
15 Correct 2439 ms 43896 KB Output is correct
16 Correct 2163 ms 43936 KB Output is correct
17 Correct 4 ms 4936 KB Output is correct
18 Correct 4 ms 4936 KB Output is correct
19 Correct 5 ms 4936 KB Output is correct
20 Correct 6 ms 4936 KB Output is correct
21 Correct 6 ms 4936 KB Output is correct
22 Correct 8 ms 4936 KB Output is correct
23 Correct 7 ms 5064 KB Output is correct
24 Correct 6 ms 4936 KB Output is correct
25 Correct 5 ms 4936 KB Output is correct
26 Correct 6 ms 5064 KB Output is correct
27 Correct 39 ms 5320 KB Output is correct
28 Correct 37 ms 5308 KB Output is correct
29 Correct 42 ms 5320 KB Output is correct
30 Correct 26 ms 5264 KB Output is correct
31 Correct 38 ms 5408 KB Output is correct
32 Correct 4 ms 4936 KB Output is correct
33 Correct 1147 ms 27292 KB Output is correct
34 Correct 2205 ms 43840 KB Output is correct
35 Correct 1335 ms 43884 KB Output is correct
36 Correct 2159 ms 43888 KB Output is correct
37 Correct 2346 ms 43884 KB Output is correct
38 Correct 1432 ms 43888 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4936 KB Output is correct
2 Correct 3 ms 4936 KB Output is correct
3 Correct 4 ms 4936 KB Output is correct
4 Correct 1087 ms 22788 KB Output is correct
5 Correct 2994 ms 43816 KB Output is correct
6 Correct 851 ms 11456 KB Output is correct
7 Correct 3095 ms 43808 KB Output is correct
8 Correct 1162 ms 18704 KB Output is correct
9 Correct 3125 ms 43864 KB Output is correct
10 Correct 2040 ms 43804 KB Output is correct
11 Correct 3298 ms 44108 KB Output is correct
12 Correct 2452 ms 43808 KB Output is correct
13 Correct 3139 ms 44028 KB Output is correct
14 Correct 3342 ms 43756 KB Output is correct
15 Correct 2439 ms 43896 KB Output is correct
16 Correct 2163 ms 43936 KB Output is correct
17 Correct 4 ms 4936 KB Output is correct
18 Correct 4 ms 4936 KB Output is correct
19 Correct 5 ms 4936 KB Output is correct
20 Correct 6 ms 4936 KB Output is correct
21 Correct 6 ms 4936 KB Output is correct
22 Correct 8 ms 4936 KB Output is correct
23 Correct 7 ms 5064 KB Output is correct
24 Correct 6 ms 4936 KB Output is correct
25 Correct 5 ms 4936 KB Output is correct
26 Correct 6 ms 5064 KB Output is correct
27 Correct 39 ms 5320 KB Output is correct
28 Correct 37 ms 5308 KB Output is correct
29 Correct 42 ms 5320 KB Output is correct
30 Correct 26 ms 5264 KB Output is correct
31 Correct 38 ms 5408 KB Output is correct
32 Correct 4 ms 4936 KB Output is correct
33 Correct 1147 ms 27292 KB Output is correct
34 Correct 2205 ms 43840 KB Output is correct
35 Correct 1335 ms 43884 KB Output is correct
36 Correct 2159 ms 43888 KB Output is correct
37 Correct 2346 ms 43884 KB Output is correct
38 Correct 1432 ms 43888 KB Output is correct
39 Correct 4 ms 4936 KB Output is correct
40 Correct 4 ms 4936 KB Output is correct
41 Correct 3 ms 4936 KB Output is correct
42 Correct 1061 ms 22828 KB Output is correct
43 Correct 3115 ms 43788 KB Output is correct
44 Correct 960 ms 11584 KB Output is correct
45 Correct 3166 ms 44004 KB Output is correct
46 Correct 1142 ms 18640 KB Output is correct
47 Correct 3016 ms 44000 KB Output is correct
48 Correct 2382 ms 43968 KB Output is correct
49 Correct 3023 ms 44016 KB Output is correct
50 Correct 2443 ms 44036 KB Output is correct
51 Correct 3182 ms 44004 KB Output is correct
52 Correct 3138 ms 43968 KB Output is correct
53 Correct 2210 ms 43800 KB Output is correct
54 Correct 2102 ms 43876 KB Output is correct
55 Correct 4 ms 4936 KB Output is correct
56 Incorrect 2271 ms 43932 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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