제출 #1178691

#제출 시각아이디문제언어결과실행 시간메모리
1178691tkm_algorithms밀림 점프 (APIO21_jumps)C++20
0 / 100
112 ms29712 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) { hh.push_back(h[i]); } for (int i = 0; i < n; ++i) { idx[h[i]] = i; uly[i][0] = kici[i][0] = h[i]; } for (int i = 0; i < n; ++i) { for (int j = 0; j < lg; ++j) { if (a[i] == -1 && b[i] == -1)continue; if (a[i] == -1)uly[i][0] = h[b[i]], kici[i][0] = h[b[i]]; else if (b[i] == -1)uly[i][0] = h[a[i]], kici[i][0] = h[a[i]]; else if (h[a[i]] > h[b[i]])uly[i][0] = h[a[i]], kici[i][0] = h[b[i]]; else uly[i][0] = h[b[i]], kici[i][0] = h[a[i]]; } } sort(h.rbegin(), h.rend()); for (int i = 0; i < n; ++i) for (int j = 1; j < lg; ++j) { uly[idx[h[i]]][j] = uly[idx[uly[idx[h[i]]][j-1]]][j-1]; kici[idx[h[i]]][j] = kici[idx[kici[idx[h[i]]][j-1]]][j-1]; //if (i == n-1)cout << uly[0][1] << nl; } //cout << uly[0][1] << nl; } int minimum_jumps(int a, int b, int c, int d) { d = idx[hh[a]]; int ans = 0; for (int i = 19; i >= 0; --i) { if ((i > 0 && uly[d][i] == uly[d][i-1]) || uly[d][i] == hh[a])continue; if (uly[d][i] <= hh[c]) { ans += (1 << i); if (uly[d][i] == hh[c])return ans; d = idx[uly[d][i]]; } } for (int i = 19; i >= 0; --i) { if ((i > 0 && kici[d][i] == kici[d][i-1]) || kici[d][i] == hh[a])continue; if (kici[d][i] <= hh[c]) { ans += (1 << i); if (kici[d][i] == hh[c])return ans; d = idx[kici[d][i]]; } } 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); //cout << uly[][] // 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...