Submission #619963

#TimeUsernameProblemLanguageResultExecution timeMemory
619963JomnoiRainforest Jumps (APIO21_jumps)C++17
0 / 100
258 ms76284 KiB
#include <bits/stdc++.h> #include "jumps.h" using namespace std; const int MAX_N = 2e5 + 5; int N; int H[MAX_N]; int pre[MAX_N][20], nxt1[MAX_N][20], nxt2[MAX_N][20]; vector <int> jump[MAX_N]; int table[MAX_N][20]; void init(int n, vector <int> h) { N = n; H[0] = H[N + 1] = N + 1; for(int i = 1; i <= N; i++) { H[i] = h[i - 1]; table[i][0] = H[i]; } for(int j = 1; j < 20; j++) { for(int i = 1; i + (1<<j) - 1 <= N; i++) { table[i][j] = max(table[i][j - 1], table[i + (1<<(j - 1))][j - 1]); } } stack <int> stk; for(int i = 1; i <= N; i++) { while(!stk.empty() and H[stk.top()] < H[i]) { jump[stk.top()].push_back(i); stk.pop(); } if(!stk.empty()) { jump[i].push_back(stk.top()); pre[i][0] = stk.top(); } stk.push(i); } for(int i = 1; i <= N; i++) { sort(jump[i].begin(), jump[i].end()); if(jump[i].size() > 0) { nxt1[i][0] = jump[i][0]; } if(jump[i].size() > 1) { nxt2[i][0] = jump[i][1]; } for(int j = 1; j < 20; j++) { pre[i][j] = pre[pre[i][j - 1]][j - 1]; nxt1[i][j] = nxt1[nxt1[i][j - 1]][j - 1]; nxt2[i][j] = nxt2[nxt2[i][j - 1]][j - 1]; } } } int getMax(int l, int r) { int j = log2(r - l + 1); return max(table[l][j], table[r - (1<<j) + 1][j]); } int getIdx(int l, int r, int mx) { for(int i = 19; i >= 0; i--) { if(l <= pre[r][i] and H[pre[r][i]] < mx) { r = pre[r][i]; } } return r; } int minimum_jumps(int A, int B, int C, int D) { A++, B++, C++, D++; int maxR = getMax(C, D); int st = getIdx(A, B, maxR); if(H[st] > maxR) { return -1; } if(B + 1 == C) { return 1; } int maxM = getMax(B + 1, C - 1); if(maxM > maxR) { return -1; } if(H[st] > maxM) { return 1; } int ans = 0; for(int i = 19; i >= 0; i--) { if(H[nxt2[st][i]] < maxM) { st = nxt2[st][i]; ans += (1<<i); } } if(H[nxt2[st][0]] < maxR) { return ans + 2; } for(int i = 19; i >= 0; i--) { if(H[nxt1[st][i]] < maxM) { st = nxt1[st][i]; ans += (1<<i); } } if(H[nxt1[st][0]] < maxR) { return ans + 2; } return -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...