# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
558996 | 2022-05-09T07:17:46 Z | LastRonin | Rainforest Jumps (APIO21_jumps) | C++14 | 1192 ms | 47892 KB |
#include "jumps.h" #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define f first #define s second using namespace std; const int N = 2e5 + 10; int bp[N][18]; int bp2[N][18]; int bp3[N][18]; int z[N], h[N]; int Le[N], Ri[N]; void init(int n, vector<int> H) { for(int j = 1; j <= n; j++) h[j] = H[j - 1]; stack<int> L, R; for(int j = 1; j <= n; j++) z[h[j]] = j; for(int i = 1; i <= n; i++) { while(L.size() && L.top() <= h[i])L.pop(); if(L.size()) Le[i] = L.top(); L.push(h[i]); } for(int i = n; i >= 1; i--) { while(R.size() && R.top() <= h[i])R.pop(); if(R.size()) Ri[i] = R.top(); R.push(h[i]); } for(int j = n; j >= 1; j--) { bp[z[j]][0] = (Le[z[j]] > Ri[z[j]] ? Le[z[j]] : Ri[z[j]]); bp2[z[j]][0] = Ri[z[j]]; bp3[z[j]][0] = Le[z[j]]; for(int i = 1; i < 18; i++) { bp[z[j]][i] = bp[z[bp[z[j]][i - 1]]][i - 1]; bp2[z[j]][i] = bp2[z[bp2[z[j]][i - 1]]][i - 1]; bp3[z[j]][i] = bp3[z[bp3[z[j]][i - 1]]][i - 1]; } } } int minimum_jumps(int A, int B, int C, int D) { A++, B++, C++, D++; ll X = B; for(int j = 17; j >= 0; j--) { if(bp2[X][j] == 0)continue; if(z[bp2[X][j]] < C) { X = z[bp2[X][j]]; } } X = z[bp2[X][0]]; if(X > D || X == 0)return -1; C = X; for(int j = 17; j >= 0; j--) { if(bp3[B][j] == 0)continue; if(bp3[B][j] <= h[C] && z[bp3[B][j]] >= A) { B = z[bp3[B][j]]; } } ll F = Le[B]; if(F >= A && Ri[F] <= D && Ri[F] >= C)return 1; ll mnans = N + 1; // if(F != 0 && Ri[F] <= D && Ri[F] >= C) mnans = 2; ll cnt = 0; for(int j = 17; j >= 0; j--) { if(bp[B][j] == 0)continue; if(bp[B][j] <= h[C]) { cnt += (1<<j); B = z[bp[B][j]]; } } for(int j = 17; j >= 0; j--) { if(bp2[B][j] == 0)continue; if(bp2[B][j] <= h[C]) { cnt += (1<<j); B = z[bp2[B][j]]; } } if(B != C)return -1; return cnt; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 336 KB | Output is correct |
2 | Correct | 0 ms | 336 KB | Output is correct |
3 | Correct | 198 ms | 37628 KB | Output is correct |
4 | Correct | 1192 ms | 47200 KB | Output is correct |
5 | Correct | 929 ms | 23868 KB | Output is correct |
6 | Correct | 1110 ms | 47312 KB | Output is correct |
7 | Correct | 837 ms | 32312 KB | Output is correct |
8 | Correct | 989 ms | 47412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 336 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 336 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 336 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 1 ms | 336 KB | Output is correct |
3 | Correct | 0 ms | 336 KB | Output is correct |
4 | Correct | 221 ms | 21768 KB | Output is correct |
5 | Correct | 852 ms | 47268 KB | Output is correct |
6 | Correct | 560 ms | 8016 KB | Output is correct |
7 | Correct | 756 ms | 47288 KB | Output is correct |
8 | Correct | 548 ms | 16416 KB | Output is correct |
9 | Correct | 999 ms | 47172 KB | Output is correct |
10 | Correct | 1063 ms | 47288 KB | Output is correct |
11 | Incorrect | 869 ms | 47892 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 1 ms | 336 KB | Output is correct |
3 | Correct | 0 ms | 336 KB | Output is correct |
4 | Correct | 221 ms | 21768 KB | Output is correct |
5 | Correct | 852 ms | 47268 KB | Output is correct |
6 | Correct | 560 ms | 8016 KB | Output is correct |
7 | Correct | 756 ms | 47288 KB | Output is correct |
8 | Correct | 548 ms | 16416 KB | Output is correct |
9 | Correct | 999 ms | 47172 KB | Output is correct |
10 | Correct | 1063 ms | 47288 KB | Output is correct |
11 | Incorrect | 869 ms | 47892 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 336 KB | Output is correct |
2 | Correct | 0 ms | 336 KB | Output is correct |
3 | Correct | 198 ms | 37628 KB | Output is correct |
4 | Correct | 1192 ms | 47200 KB | Output is correct |
5 | Correct | 929 ms | 23868 KB | Output is correct |
6 | Correct | 1110 ms | 47312 KB | Output is correct |
7 | Correct | 837 ms | 32312 KB | Output is correct |
8 | Correct | 989 ms | 47412 KB | Output is correct |
9 | Incorrect | 0 ms | 336 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |