Submission #857435

#TimeUsernameProblemLanguageResultExecution timeMemory
857435chanhchuong123Rainforest Jumps (APIO21_jumps)C++14
44 / 100
762 ms45252 KiB
#include <bits/stdc++.h> using namespace std; #define task "" const int MAX = 200020; int n, q; stack<int> st; int H[MAX], dp[18][MAX]; int rg[18][MAX], hg[18][MAX]; #define combine(x, y) (x == -1 ? y : y == -1 ? x : H[x] > H[y] ? x : y) 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]); } void init(int _n, vector<int> _H) { n = _n; for (int i = 0; i < n; ++i) { H[i] = _H[i]; } st = stack<int> {}; for (int i = 0; i <= n - 1; ++i) { while (st.size() && H[st.top()] < H[i]) st.pop(); hg[0][i] = st.size() ? st.top() : -1; st.push(i); } st = stack<int> {}; for (int i = n - 1; i >= 0; --i) { while (st.size() && H[st.top()] < H[i]) st.pop(); rg[0][i] = st.size() ? st.top() : -1; st.push(i); } for (int i = 0; i < n; ++i) { dp[0][i] = i; hg[0][i] = combine(hg[0][i], rg[0][i]); } for (int j = 1; j <= 17; ++j) { for (int i = 0; i < n; ++i) { if (hg[j - 1][i] != -1) hg[j][i] = hg[j - 1][hg[j - 1][i]]; else hg[j][i] = -1; if (rg[j - 1][i] != -1) rg[j][i] = rg[j - 1][rg[j - 1][i]]; else rg[j][i] = -1; if (i + (1 << j) <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]); } } } int minimum_jumps(int A, int B, int C, int D) { int BC = getMax(B, C - 1), CD = getMax(C, D); 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), res = 0; for (int j = 17; j >= 0; --j) if (hg[j][st] != -1) { if (H[hg[j][st]] < H[CD]) { st = hg[j][st]; res += 1 << j; } } for (int j = 17; j >= 0; --j) if (rg[j][st] != -1) { if (rg[j][st] < C) { st = rg[j][st]; res += 1 << j; } } res += 1; st = rg[0][st]; return res; }

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:42:91: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |             if (i + (1 << j) <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                                         ~~^~~
jumps.cpp:10:34: note: in definition of macro 'combine'
   10 | #define combine(x, y) (x == -1 ? y : y == -1 ? x : H[x] > H[y] ? x : y)
      |                                  ^
jumps.cpp:42:91: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |             if (i + (1 << j) <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                                         ~~^~~
jumps.cpp:10:38: note: in definition of macro 'combine'
   10 | #define combine(x, y) (x == -1 ? y : y == -1 ? x : H[x] > H[y] ? x : y)
      |                                      ^
jumps.cpp:42:91: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |             if (i + (1 << j) <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                                         ~~^~~
jumps.cpp:10:61: note: in definition of macro 'combine'
   10 | #define combine(x, y) (x == -1 ? y : y == -1 ? x : H[x] > H[y] ? x : y)
      |                                                             ^
jumps.cpp:42:91: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   42 |             if (i + (1 << j) <= n) dp[j][i] = combine(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
      |                                                                                         ~~^~~
jumps.cpp:10:70: note: in definition of macro 'combine'
   10 | #define combine(x, y) (x == -1 ? y : y == -1 ? x : H[x] > H[y] ? x : y)
      |                                                                      ^
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         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...