Submission #1020819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020819		MohamedFaresNebili	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	4101 ms	86088 KiB

jumps

    #include <bits/stdc++.h>
         
        		using namespace std;
         
        		int N;
                int P[200005];
                vector<int> ST[800005];
        		vector<int> adj[200005];
                int UP[200005][20], DN[200005][20];
        		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++]);
                        }
                    }
                }
     
                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;
                    
     
                    build(1, 1, N);
         
        			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);
     
                        UP[_H[l]][0] = (i != -1 ? _H[i] : N + 1);
                        DN[_H[l]][0] = (j != 1e9 + 7 ? _H[j] : N + 1);
     
                        if(UP[_H[l]][0] < DN[_H[l]][0]) 
                            swap(UP[_H[l]][0], DN[_H[l]][0]);
        			}
     
                    for(int l = 1; l < 20; l++)
                        for(int i = 0; i < _N; i++) {
                            UP[H[i]][l] = UP[UP[H[i]][l - 1]][l - 1];
                            DN[H[i]][l] = DN[DN[H[i]][l - 1]][l - 1];
                        }
        		}
     
                int solve(int U, int V) {
                    if(U > V) return N + 1;
                    int best = 0;
                    for(int l = 19; l >= 0; l--)
                        if(UP[U][l] < V) best += (1 << l), U = UP[U][l];
                    
                    if(UP[U][0] == V) return best + 1;
                    if(DN[U][0] == V) return best + 1;
                    if(DN[U][0] > V) return N + 1;
                    return best + 1 + solve(DN[U][0], V);
                }
         
        		int minimum_jumps(int A, int B, int C, int D) {
                    int U = H[A], V = H[C];
                    int res = solve(U, V);
        			return (res > N ? -1 : res);
        		}

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:20:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |                     while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                           ~~^~~~~~~~~~~~~~~~~~
jumps.cpp:20:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |                     while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                                                   ~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:21:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |                         if(i == ST[v * 2].size())
      |                            ~~^~~~~~~~~~~~~~~~~~~
jumps.cpp:23:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |                         else if(j == ST[v * 2 + 1].size())
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int queryR(int, int, int, int, int, int)':
jumps.cpp:37:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                         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