oj.uz

Submission #415221

# Submission time Handle Problem Language Result Execution time Memory
415221 2021-05-31T17:18:54 Z A_D Rainforest Jumps (APIO21_jumps) C++14
23 / 100
 3826 ms 51788 KB 
#include "jumps.h"

#include <bits/stdc++.h>

using namespace std;
const int NN=2e5+100;
const int L=23;
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 ans=dfs(a[A],a[C]);
    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 4 ms 4936 KB Output is correct
2 Correct 5 ms 4936 KB Output is correct
3 Incorrect 1095 ms 42616 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 4 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 3 ms 4936 KB Output is correct
2 Correct 5 ms 4936 KB Output is correct
3 Correct 4 ms 4936 KB Output is correct
4 Correct 1353 ms 26416 KB Output is correct
5 Correct 3757 ms 51588 KB Output is correct
6 Correct 1085 ms 12792 KB Output is correct
7 Correct 3387 ms 51540 KB Output is correct
8 Correct 1455 ms 21296 KB Output is correct
9 Correct 3640 ms 51652 KB Output is correct
10 Correct 2522 ms 51556 KB Output is correct
11 Correct 3826 ms 51576 KB Output is correct
12 Correct 2508 ms 51684 KB Output is correct
13 Correct 3420 ms 51564 KB Output is correct
14 Correct 3628 ms 51708 KB Output is correct
15 Correct 2266 ms 51660 KB Output is correct
16 Correct 2522 ms 51660 KB Output is correct
17 Correct 4 ms 4892 KB Output is correct
18 Correct 4 ms 4936 KB Output is correct
19 Correct 8 ms 4936 KB Output is correct
20 Correct 7 ms 4936 KB Output is correct
21 Correct 6 ms 4936 KB Output is correct
22 Correct 9 ms 4936 KB Output is correct
23 Correct 8 ms 4936 KB Output is correct
24 Correct 6 ms 4936 KB Output is correct
25 Correct 5 ms 4936 KB Output is correct
26 Correct 8 ms 5164 KB Output is correct
27 Correct 41 ms 5448 KB Output is correct
28 Correct 45 ms 5448 KB Output is correct
29 Correct 34 ms 5448 KB Output is correct
30 Correct 26 ms 5460 KB Output is correct
31 Correct 24 ms 5448 KB Output is correct
32 Correct 4 ms 4936 KB Output is correct
33 Correct 1200 ms 31836 KB Output is correct
34 Correct 2329 ms 51548 KB Output is correct
35 Correct 1444 ms 51648 KB Output is correct
36 Correct 2383 ms 51608 KB Output is correct
37 Correct 2510 ms 51544 KB Output is correct
38 Correct 1454 ms 51724 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4936 KB Output is correct
2 Correct 5 ms 4936 KB Output is correct
3 Correct 4 ms 4936 KB Output is correct
4 Correct 1353 ms 26416 KB Output is correct
5 Correct 3757 ms 51588 KB Output is correct
6 Correct 1085 ms 12792 KB Output is correct
7 Correct 3387 ms 51540 KB Output is correct
8 Correct 1455 ms 21296 KB Output is correct
9 Correct 3640 ms 51652 KB Output is correct
10 Correct 2522 ms 51556 KB Output is correct
11 Correct 3826 ms 51576 KB Output is correct
12 Correct 2508 ms 51684 KB Output is correct
13 Correct 3420 ms 51564 KB Output is correct
14 Correct 3628 ms 51708 KB Output is correct
15 Correct 2266 ms 51660 KB Output is correct
16 Correct 2522 ms 51660 KB Output is correct
17 Correct 4 ms 4892 KB Output is correct
18 Correct 4 ms 4936 KB Output is correct
19 Correct 8 ms 4936 KB Output is correct
20 Correct 7 ms 4936 KB Output is correct
21 Correct 6 ms 4936 KB Output is correct
22 Correct 9 ms 4936 KB Output is correct
23 Correct 8 ms 4936 KB Output is correct
24 Correct 6 ms 4936 KB Output is correct
25 Correct 5 ms 4936 KB Output is correct
26 Correct 8 ms 5164 KB Output is correct
27 Correct 41 ms 5448 KB Output is correct
28 Correct 45 ms 5448 KB Output is correct
29 Correct 34 ms 5448 KB Output is correct
30 Correct 26 ms 5460 KB Output is correct
31 Correct 24 ms 5448 KB Output is correct
32 Correct 4 ms 4936 KB Output is correct
33 Correct 1200 ms 31836 KB Output is correct
34 Correct 2329 ms 51548 KB Output is correct
35 Correct 1444 ms 51648 KB Output is correct
36 Correct 2383 ms 51608 KB Output is correct
37 Correct 2510 ms 51544 KB Output is correct
38 Correct 1454 ms 51724 KB Output is correct
39 Correct 5 ms 4976 KB Output is correct
40 Correct 4 ms 4936 KB Output is correct
41 Correct 5 ms 4936 KB Output is correct
42 Correct 1062 ms 26292 KB Output is correct
43 Correct 3353 ms 51540 KB Output is correct
44 Correct 1036 ms 12864 KB Output is correct
45 Correct 3648 ms 51660 KB Output is correct
46 Correct 1165 ms 21292 KB Output is correct
47 Correct 3428 ms 51576 KB Output is correct
48 Correct 2361 ms 51788 KB Output is correct
49 Correct 3282 ms 51644 KB Output is correct
50 Correct 2610 ms 51644 KB Output is correct
51 Correct 3109 ms 51652 KB Output is correct
52 Correct 3564 ms 51736 KB Output is correct
53 Correct 2566 ms 51752 KB Output is correct
54 Correct 2337 ms 51560 KB Output is correct
55 Correct 4 ms 4936 KB Output is correct
56 Incorrect 2410 ms 51536 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

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