제출 #858349

#제출 시각아이디문제언어결과실행 시간메모리
858349chanhchuong123밀림 점프 (APIO21_jumps)C++14
48 / 100
817 ms45392 KiB
#include <bits/stdc++.h> using namespace std; #define task "" const int MAX = 200020; int n, q; int H[MAX]; stack<int> st; int dp[18][MAX], rg[18][MAX], hi[18][MAX]; #define combine(x, y) (H[(x)] < H[(y)] ? y : x) void init(int N, vector<int> _H) { n = N; for (int i = 0; i < n; ++i) { H[i + 1] = _H[i]; } H[0] = H[n + 1] = n + 1; st.push(0); for (int i = 1; i <= n; ++i) { while (H[st.top()] < H[i]) st.pop(); hi[0][i] = st.top(); st.push(i); } st.push(n + 1); rg[0][0] = rg[0][n + 1] = n + 1; for (int i = n; i >= 1; --i) { while (H[st.top()] < H[i]) st.pop(); rg[0][i] = st.top(); st.push(i); } for (int i = 1; i <= n; ++i) { dp[0][i] = i; hi[0][i] = combine(hi[0][i], rg[0][i]); } for (int j = 1; j <= 17; ++j) { for (int i = 0; i <= n + 1; ++i) { hi[j][i] = hi[j - 1][hi[j - 1][i]]; rg[j][i] = rg[j - 1][rg[j - 1][i]]; if (i + (1 << j) - 1 <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]); } } } int getMax(int l, int r) { int k = 31 - __builtin_clz(r - l + 1); return combine(dp[k][l], dp[k][r - (1 << k) + 1]); } bool in(int x, int C, int D) { return C <= x && x <= D; } int minimum_jumps(int A, int B, int C, int D) { ++A; ++B; ++C; ++D; int CD = getMax(C, D); int BC = getMax(B, C - 1); if (H[BC] > H[CD]) return -1; int l = A - 1, r = B; while (r - l > 1) { int mid = l + r >> 1; if (H[getMax(mid, B)] < H[CD]) r = mid; else l = mid; } int st = getMax(r, B); if (in(st, C, D)) return 1; int res = 0; for (int j = 17; j >= 0; --j) if (rg[0][hi[j][st]] < C) { st = hi[j][st]; res += 1 << j; } int nt = hi[0][st]; if (rg[0][nt] <= D) { st = nt; ++res; if (in(rg[0][nt], C, D)) return res + 1; } for (int j = 17; j >= 0; --j) if (rg[j][st] < C) { st = rg[j][st]; res += 1 << j; } return res + 1; }

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

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:36:95: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |             if (i + (1 << j) - 1 <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                                             ~~^~~
jumps.cpp:10:36: note: in definition of macro 'combine'
   10 | #define combine(x, y) (H[(x)] < H[(y)] ? y : x)
      |                                    ^
jumps.cpp:36:95: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |             if (i + (1 << j) - 1 <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                                             ~~^~~
jumps.cpp:10:42: note: in definition of macro 'combine'
   10 | #define combine(x, y) (H[(x)] < H[(y)] ? y : x)
      |                                          ^
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...