Submission #792079

#TimeUsernameProblemLanguageResultExecution timeMemory
792079peijarRailway Trip (JOI17_railway_trip)C++17
0 / 100
123 ms34368 KiB
#include <bits/stdc++.h> #define int long long using namespace std; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif const int MAXN = 1e5; const int MAXP = 20; int goleft[MAXP][MAXN], goright[MAXP][MAXN]; signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int N, K, Q; cin >> N >> K >> Q; vector<int> level(N); for (int &x : level) cin >> x; for (int i = 0; i < N; ++i) { int j = i - 1; while (j >= 0 and level[j] < level[i]) j = goleft[0][j]; goleft[0][i] = j; } for (int i = N - 1; i >= 0; --i) { int j = i + 1; while (j < N and level[j] < level[i]) j = goright[0][j]; goright[0][i] = j; } for (int p = 0; p < MAXP - 1; ++p) for (int i = 0; i < N; ++i) { int L = goleft[p][i]; int R = goright[p][i]; if (L != -1) goleft[p + 1][i] = goleft[p][L]; else goleft[p + 1][i] = -1; if (R != N) goleft[p + 1][i] = min(goleft[p + 1][i], goleft[p][R]); if (R != N) goright[p + 1][i] = goright[p][R]; else goright[p + 1][i] = N; if (L != -1) goright[p + 1][i] = max(goright[p + 1][i], goright[p][L]); } while (Q--) { int A, B; cin >> A >> B; --A, --B; if (A > B) swap(A, B); int sol = 0; for (int p = MAXP - 1; p >= 0; --p) if (goright[p][A] <= B) { sol += 1 << p; A = goright[p][A]; } for (int p = MAXP - 1; p >= 0; --p) if (goleft[p][B] >= A) { sol += 1 << p; B = goleft[p][B]; } if (A < B) sol++; cout << sol - 1 << '\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...