Submission #1022283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022283		MohamedFaresNebili	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	387 ms	88924 KiB

jumps

#include <bits/stdc++.h>
                         
        using namespace std;
 
        int N;
        int P[200005];
        int MX[800005];
        vector<int> ST[800005];
        vector<int> adj[200005];
        int UP[200005][20], DN[200005][20];
        int R[200005];
        vector<int> H;
 
        void build(int v, int l, int r) {
            if(l == r) {
                ST[v].push_back(P[l]);
                return;
            }
            build(v * 2, l, (l + r) / 2);
            build(v * 2 + 1, (l + r) / 2 + 1, r);
            
            int i = 0, j = 0;
            while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
                if(i == ST[v * 2].size())
                    ST[v].push_back(ST[v * 2 + 1][j++]);
                else if(j == ST[v * 2 + 1].size())
                    ST[v].push_back(ST[v * 2][i++]);
                else {
                    if(ST[v * 2][i] < ST[v * 2 + 1][j])
                        ST[v].push_back(ST[v * 2][i++]);
                    else ST[v].push_back(ST[v * 2 + 1][j++]);
                }
            }
        }
 
        void buildM(int v, int l, int r) {
            if(l == r) {
                MX[v] = H[l];
                return;
            }
            buildM(v * 2, l, (l + r) / 2);
            buildM(v * 2 + 1, (l + r) / 2 + 1, r);
            MX[v] = max(MX[v * 2], MX[v * 2 + 1]);
        }
 
        int query(int v, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return 0;
            if(l >= lo && r <= hi) return MX[v];
            return max(query(v * 2, l, (l + r) / 2, lo, hi),
                query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
        }
 
        int queryR(int v, int l, int r, int lo, int hi, int K) {
            if(l > hi || r < lo) return 1e9 + 7;
            if(l >= lo && r <= hi) {
                int R = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
                if(R == ST[v].size()) return 1e9 + 7;
                return ST[v][R];
            }
            return min(queryR(v * 2, l, (l + r) / 2, lo, hi, K), 
                queryR(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K));
        }
 
        int queryL(int v, int l, int r, int lo, int hi, int K) {
            if(l > hi || r < lo) return -1;
            if(l >= lo && r <= hi) {
                int L = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
                if(L == 0) return -1;
                return ST[v][--L];
            }
            return max(queryL(v * 2, l, (l + r) / 2, lo, hi, K), 
                queryL(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, K));
        }
 
        void init(int _N, vector<int> _H) {
            N = _N;
            for(int l = 0; l < _N; l++) {
                H.push_back(_H[l]);
                P[_H[l]] = l;
            }
 
            for(int l = 0; l < 20; l++)
                UP[N + 1][l] = DN[N + 1][l] = N + 1;
            R[N + 1] = N + 1;
            
 
            build(1, 1, N);
            buildM(1, 0, N - 1);
 
            for(int l = 0; l < _N; l++) {
                int i = queryL(1, 1, N, _H[l] + 1, N, l);
                int j = queryR(1, 1, N, _H[l] + 1, N, l);
 
                DN[l][0] = (i != -1 ? i : N + 1);
                UP[l][0] = (j != 1e9 + 7 ? j : N + 1);
                R[l] = UP[l][0];
 
                if(H[UP[l][0]] < H[DN[l][0]]) 
                    swap(UP[l][0], DN[l][0]);
 
            }

            H[N + 1] = 1e9 + 7;
 
            for(int l = 1; l < 20; l++)
                for(int i = 0; i < _N; i++) {
                    UP[i][l] = UP[UP[i][l - 1]][l - 1];
                    DN[i][l] = DN[DN[i][l - 1]][l - 1];
                }
        }
 
        int solve(int U, int C, int D, int G) {
            int best = 0;
            if(R[U] >= C) return 1;
 
            for(int l = 19; l >= 0; l--)
                if(H[UP[U][l]] < G) best += (1 << l), U = UP[U][l];
            if(U >= C && U <= D) return best;
            ++best; U = UP[U][0];
            if(U >= C && U <= D) return best;
 
            for(int l = 19; l >= 0; l--) 
                if(H[DN[U][l]] < G) best += (1 << l), U = DN[U][l];
            if(U >= C && U <= D) return best;
            ++best; U = DN[U][0];
            if(U >= C && U <= D) return best;
            return -1;
        }
 
        int minimum_jumps(int A, int B, int C, int D) {
            int lo = A, hi = B, ans = -1;
            int G = query(1, 0, N - 1, C, D);
            while(lo <= hi) {
                int md = (lo + hi) / 2;
                int q = query(1, 0, N - 1, md, B);
                if(q < G) ans = md, hi = md - 1;
                else lo = md + 1;
            }
            if(ans == -1) return -1;
            int U = P[query(1, 0, N - 1, ans, B)];
            int res = solve(U, C, D, G);
            return res;
        }

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                   ~~^~~~~~~~~~~~~~~~~~
jumps.cpp:23:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                                           ~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |                 if(i == ST[v * 2].size())
      |                    ~~^~~~~~~~~~~~~~~~~~~
jumps.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |                 else if(j == ST[v * 2 + 1].size())
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int queryR(int, int, int, int, int, int)':
jumps.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(R == ST[v].size()) return 1e9 + 7;
      |                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19