oj.uz

Submission #541784

# Submission time Handle Problem Language Result Execution time Memory
541784 2022-03-24T11:42:28 Z Pherokung Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 286 ms 48840 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
typedef pair<int,int> pa;

int n,h[200005],nex[200005][20],pow_2[20],nex_r[200005][20],l_mx[200005],r_mx[200005],hsh[200005];
stack<pair<int,int> > stk;

struct node{
    node *l,*r;
    int mx,mi;
};
node top;

void build(node *pos,int be,int ed){
    if(be == ed){
        pos->mi = h[be];
        pos->mx = h[be];
        return;
    }

    int mid = (be+ed)/2;
    pos->l = new node;
    pos->r = new node;

    build(pos->l,be,mid);
    build(pos->r,mid+1,ed);

    pos->mi = min(pos->l->mi,pos->r->mi);
    pos->mx = max(pos->l->mx,pos->r->mx);
}

pa query(node *pos,int be,int ed,int x,int y){
    if(be > ed ||  y < be || ed < x) return {n+1,0};
    if(x <= be && ed <= y) return {pos->mi,pos->mx};

    int mid = (be+ed)/2;
    pa L = query(pos->l,be,mid,x,y);
    pa R = query(pos->r,mid+1,ed,x,y);

    return {min(L.F,R.F),max(L.S,R.S)};
}

void init(int N, vector<int> H) {
    n = N;
    for(int i=0;i<N;i++) h[i+1] = H[i], hsh[H[i]] = i+1;
    h[n+1] = n+1;
    h[0] = n+1;


    build(&top,1,n);
    pow_2[0] = 1;
    for(int i=1;i<=20;i++) pow_2[i] = pow_2[i-1] * 2;

    stk.push({n+1,0});
    for(int i=1;i<=n;i++){
        while(stk.top().F < h[i]) stk.pop();
        nex[i][0] = stk.top().S;
        stk.push({h[i],i});
    }
    while(!stk.empty()) stk.pop();

    stk.push({n+1,n+1});
    for(int i=n;i>=1;i--){
        while(stk.top().F < h[i]) stk.pop();
        nex_r[i][0] = stk.top().S;
        if(stk.top().F > h[nex[i][0]]) nex[i][0] = stk.top().S;
        stk.push({h[i],i});
    }
    while(!stk.empty()) stk.pop();

    for(int i=1;i<=18;i++){
        for(int j=1;j<=n;j++){
            nex[j][i] = nex[nex[j][i-1]][i-1];
            nex_r[j][i] = nex_r[nex_r[j][i-1]][i-1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    A++, B++, C++, D++;
    pa val_st = query(&top,1,n,A,B);
    pa val_mid = query(&top,1,n,B+1,C-1);
    pa val_ed = query(&top,1,n,C,D);

    //printf(">>%d %d %d\n",val_st.S,val_mid.S,val_ed.S);
    if(val_mid.S > val_ed.S) return -1;

    int be,ed,mid,mx_st,val,mi_ed,p,ans;
    be = C-1, ed = D+1, mi_ed = n+1,ans = 0;
    while(ed-be > 1){
        mid = (be+ed)/2;
        val = query(&top,1,n,C,mid).S;

        if(val > val_mid.S){
            ed = mid;
            mi_ed = min(mi_ed,val);
        }
        else be = mid;
    }

    //printf(">>%d\n",mi_ed);
    if(val_st.S > val_ed.S){
        if(val_mid.S < h[B]) return -1;
        be = A-1, ed = B+1, mx_st = 0;
        while(ed-be > 1){
            mid = (be+ed)/2;
            val = query(&top,1,n,mid,B).S;

            if(val < val_ed.S){
                ed = mid;
                mx_st = max(mx_st,val);
            }
            else be = mid;
        }

        //printf("!!!%d\n",mx_st);
        p = hsh[mx_st];
        for(int i=18;i>=0;i--){
            if(nex_r[p][i] < C){
                ans += pow_2[i];
                p = nex_r[p][i];
            }
        }
        ans++;

        return ans;
    }
    else{
        mx_st = val_st.S;
        int pos1 = hsh[val_mid.S];
        int pos2 = 0;
        int dis0=0,dis1=0,dis2=0;
        be = 0, ed = A;
        while(ed-be > 1){
            mid = (be+ed)/2;
            val = query(&top,1,n,mid,A-1).S;

            if(val > val_mid.S){
                be = mid;
                pos2 = max(pos2,val);

            }
            else ed = mid;
        }
        pos2 = hsh[pos2];

        //printf("pos1 = %d, pos2 = %d\n",pos1,pos2);

        if(val_mid.S > val_st.S){
            dis1 = 0;
            p = hsh[mx_st];
            for(int i=18;i>=0;i--){
                if(h[nex[p][i]] < h[pos1]){
                    dis1 += pow_2[i];
                    p = nex[p][i];
                }
            }
            dis1 += 2;
        }
        else dis1 = 1;

        if(pos2 != 0){
            dis2 = 0;
            p = hsh[mx_st];
            for(int i=18;i>=0;i--){
                if(h[nex[p][i]] < h[pos2]){
                    dis2 += pow_2[i];
                    p = nex[p][i];
                }
            }
            dis2 += 2;
        }
        else dis2 = 1e9;

        return min(dis1,dis2);
    }
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:136:13: warning: unused variable 'dis0' [-Wunused-variable]
  136 |         int dis0=0,dis1=0,dis2=0;
      |             ^~~~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:56:37: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   56 |     for(int i=1;i<=20;i++) pow_2[i] = pow_2[i-1] * 2;
      |                            ~~~~~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:56:18: note: within this loop
   56 |     for(int i=1;i<=20;i++) pow_2[i] = pow_2[i-1] * 2;
      |                 ~^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 257 ms 38988 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 2 ms 208 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 2 ms 208 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 81 ms 38144 KB Output is correct
6 Correct 94 ms 47264 KB Output is correct
7 Correct 47 ms 24356 KB Output is correct
8 Correct 95 ms 47268 KB Output is correct
9 Correct 11 ms 7344 KB Output is correct
10 Correct 112 ms 47264 KB Output is correct
11 Incorrect 111 ms 48840 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 286 ms 21768 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Incorrect 286 ms 21768 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 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 257 ms 38988 KB Output isn't correct
4 Halted 0 ms 0 KB -