제출 #1021037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021037		MohamedFaresNebili	밀림 점프 (APIO21_jumps)	C++14	0 / 100	11 ms	23928 KiB

jumps

    #include <bits/stdc++.h>
                
                    using namespace std;
                
                    int N;
                    int P[200005];
                    int MX[800005];
                    int L[200005], R[200005];
                    int par[200005][20];
                    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++]);
                            }
                        }
                    }
            
                    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 rf = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
                            if(rf == ST[v].size()) return 1e9 + 7;
                            return ST[v][rf];
                        }
                        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 lf = lower_bound(ST[v].begin(), ST[v].end(), K) - ST[v].begin();
                            if(lf == 0) return -1;
                            return ST[v][--lf];
                        }
                        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++) {
                            R[N + 1] = N + 1, L[N + 1] = N + 1;
                            UP[N + 1][l] = DN[N + 1][l] = N + 1;
                            par[N + 1][l] = 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);
            
                            L[l] = UP[l][0] = (i != -1 ? i : N + 1);
                            R[l] = DN[l][0] = (j != 1e9 + 7 ? j : N + 1);
                            par[l][0] = R[l];
            
                            if(_H[R[l]] < _H[L[l]]) 
                                swap(UP[l][0], DN[l][0]);
                        }
            
                        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];
                                par[i][l] = par[par[i][l - 1]][l - 1];
                            }
                    }
            
                    int solve(int U, int C, int D) {
                        int best = 0;
                        if(R[U] >= C) return 1;
            
                        for(int l = 19; l >= 0; l--)
                            if(R[UP[U][l]] < C) best += (1 << l), U = UP[U][l];
         
                        if(R[L[U]] >= C && R[L[U]] <= D) return 2 + best;
            
                        for(int l = 19; l >= 0; l--) 
                            if(par[U][l] < C) best += (1 << l), U = par[U][l];
            
                        U = par[U][0];
                        if(U >= C && U <= D) return 1 + 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); G =P[G];
                        ans = query(1, 0, N - 1, max(L[G] + 1, A), B);
                        if(ans == 0) return -1;
                      int U = P[ans];
                        int res = solve(U, C, D);
                        return (res > N ? -1 : res);
                    }

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:24:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |                         while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                               ~~^~~~~~~~~~~~~~~~~~
jumps.cpp:24:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |                         while(i < ST[v * 2].size() || j < ST[v * 2 + 1].size()) {
      |                                                       ~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:25:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |                             if(i == ST[v * 2].size())
      |                                ~~^~~~~~~~~~~~~~~~~~~
jumps.cpp:27:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |                             else if(j == ST[v * 2 + 1].size())
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int queryR(int, int, int, int, int, int)':
jumps.cpp:58:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                             if(rf == ST[v].size()) return 1e9 + 7;
      |                                ~~~^~~~~~~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:133:29: warning: unused variable 'lo' [-Wunused-variable]
  133 |                         int lo = A, hi = B, ans = -1;
      |                             ^~
jumps.cpp:133:37: warning: unused variable 'hi' [-Wunused-variable]
  133 |                         int lo = A, hi = B, ans = -1;
      |                                     ^~

• 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