Submission #1231074

#TimeUsernameProblemLanguageResultExecution timeMemory
1231074duckindogRailway Trip (JOI17_railway_trip)C++20
100 / 100
84 ms14920 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int n, k, q; int l[N]; const int LG = 16; int L[N][LG + 1], R[N][LG + 1]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k >> q; for (int i = 1; i <= n; ++i) cin >> l[i]; { // RMQ { // left stack<int> st; for (int i = 1; i <= n; ++i) { while (st.size() && l[st.top()] < l[i]) st.pop(); L[i][0] = (!st.size() ? 1 : st.top()); st.push(i); } } { // right stack<int> st; for (int i = n; i >= 1; --i) { while (st.size() && l[st.top()] < l[i]) st.pop(); R[i][0] = (!st.size() ? n : st.top()); st.push(i); } } for (int j = 1; j <= LG; ++j) { for (int i = 1; i <= n; ++i) { L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]); R[i][j] = max(R[L[i][j - 1]][j - 1], R[R[i][j - 1]][j - 1]); } } } while (q--) { int a, b; cin >> a >> b; if (a > b) swap(a, b); int answer = 0; int l = a, r = a; for (int i = LG; i >= 0; --i) { if (max(R[l][i], R[r][i]) < b) { tie(l, r) = make_pair(min(L[l][i], L[r][i]), max(R[l][i], R[r][i])); answer += (1 << i); } } int preR = r; l = b, r = b; for (int i = LG; i >= 0; --i) { if (min(L[l][i], L[r][i]) > preR) { tie(l, r) = make_pair(min(L[l][i], L[r][i]), max(R[l][i], R[r][i])); answer += (1 << i); } } cout << answer << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...