제출 #1020742

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

jumps

#include <bits/stdc++.h>
     
    		using namespace std;
     
    		int N;
            int P[200005];
            vector<int> ST[800005];
    		vector<int> adj[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++]);
                    }
                }
            }

            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;
                }
                

                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);
                    if(i != -1) adj[l].push_back(i);
                    if(j != 1e9 + 7) adj[l].push_back(j);
    			}
    		}
     
    		int minimum_jumps(int A, int B, int C, int D) {
    			vector<int> dis(N, 1e9 + 7); priority_queue<pair<int, int>> Q;
    			for(int l = A; l <= B; l++) {
    				dis[l] = 0; Q.push({0, l});
    			}
    			while(!Q.empty()) {
    				pair<int, int> U = Q.top(); Q.pop();
    				if(-U.first > dis[U.second]) continue;
    				if(U.second >= C && U.second <= D) return -U.first;
    				for(auto V : adj[U.second]) {
    					if(dis[U.second] + 1 < dis[V]) {
    						dis[V] = dis[U.second] + 1;
    						Q.push({-dis[V], V});
    					}
    				}
    			}
    			return -1;
    		}

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

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

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