Submission #1178520

#TimeUsernameProblemLanguageResultExecution timeMemory
1178520tkm_algorithmsRainforest Jumps (APIO21_jumps)C++20
0 / 100
0 ms424 KiB
/** * In the name of Allah * We are nothing and you're everything **/ #include <bits/stdc++.h> //#include "jumps.h" using namespace std; #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; //#define int ll const char nl = '\n'; const int N = 2e5; const int inf = 1e9; const int lg = 20; int uly[N+2][lg], kici[N+2][lg]; vector<int> hh; int idx[N+2]; int nn; void init(int n, vector<int> h) { nn = n; stack<int> st; vector<int> a(n, -1), b(n, -1); for (int i = n-1; i >= 0; --i) { while (!st.empty() && h[st.top()] <= h[i])st.pop(); if (!st.empty())a[i] = st.top(); st.push(i); } while (!st.empty())st.pop(); for (int i = 0; i < n; ++i) { while (!st.empty() && h[st.top()] <= h[i])st.pop(); if (!st.empty())b[i] = st.top(); st.push(i); } for (int i = 0; i < n; ++i) for (int j = 0; j < lg; ++j)uly[i][j] = kici[i][j] = N+1; for (int i = 0; i < lg; ++i)uly[N+1][i] = kici[N+1][i] = N+1; for (int i = 0; i < n; ++i) { if (a[i] == -1 && b[i] == -1)uly[i][0] = kici[i][0] = i; else if (a[i] == -1)uly[i][0] = b[i], kici[i][0] = b[i]; else if (b[i] == -1)uly[i][0] = a[i], kici[i][0] = a[i]; else if (h[a[i]] > h[b[i]])uly[i][0] = a[i], kici[i][0] = b[i]; else uly[i][0] = b[i], kici[i][0] = a[i]; } for (int i = 0; i < n; ++i) { hh.push_back(h[i]); idx[h[i]] = i; } sort(h.rbegin(), h.rend()); for (int i = 0; i < n; ++i) { for (int j = 1; j < lg; ++j) { //if (uly[i][j-1] != i) int ind = idx[h[i]]; uly[ind][j] = uly[uly[ind][j-1]][j-1]; //if (kici[i][j-1] != i) kici[ind][j] = kici[kici[ind][j-1]][j-1]; }; } } int minimum_jumps(int a, int b, int c, int d) { d = hh[c]; if (hh[a] > d)return -1; int ans = 0; for (int i = 19; i >= 0; --i) { if ((i > 0 && uly[a][i] == uly[a][i-1]) || uly[a][i] == a)continue; if (uly[a][i] <= d) { //cout << a << " " << i << " " << uly[a][i] << nl; a = idx[uly[a][i]]; ans += (1 << i); } } if (a == c)return ans; for (int i = 19; i >= 0; --i) { if (i > 0 && kici[a][i] == kici[a][i-1])continue; if (kici[a][i] <= d) { a = idx[kici[a][i]]; ans += (1 << i); } } if (a == d)return ans; return -1; } //int main() { //int n, q; cin >> n >> q; //vector<int> h(n); //for (int i = 0; i < n; ++i)cin >> h[i]; //init(n, h); //while (q--) { //int a, b, c, d; cin >> a >> b >> c >> d; //cout << minimum_jumps(a, b, c, d) << nl; //} //}
#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...