Submission #1274347

#TimeUsernameProblemLanguageResultExecution timeMemory
1274347MisterReaperRailway Trip 2 (JOI22_ho_t4)C++20
0 / 100
171 ms106936 KiB
// File railwaytrip.cpp created on 29.09.2025 at 21:19:43 #include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif template<typename T> bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } constexpr int max_N = int(1E5) + 5; int logs[max_N]; struct SparseTable { int n; std::vector<std::vector<int>> mat; SparseTable() {} SparseTable(std::vector<int>& x) : n(x.size()) { int lg = logs[n] + 1; mat.resize(lg); mat[0].resize(n); for (int i = 0; i < n; ++i) { mat[0][i] = x[i]; } for (int i = 1; i < lg; ++i) { int m = n - (1 << i) + 1; mat[i].resize(m); for (int j = 0; j < m; ++j) { mat[i][j] = std::max(mat[i - 1][j], mat[i - 1][j + (1 << (i - 1))]); } } } void init(std::vector<int>& x) { n = int(x.size()); int lg = logs[n] + 1; mat.resize(lg); mat[0].resize(n); for (int i = 0; i < n; ++i) { mat[0][i] = x[i]; } for (int i = 1; i < lg; ++i) { int m = n - (1 << i) + 1; mat[i].resize(m); for (int j = 0; j < m; ++j) { mat[i][j] = std::max(mat[i - 1][j], mat[i - 1][j + (1 << (i - 1))]); } } } int get(int l, int r) { int d = r - l + 1; int lg = logs[d]; return std::max(mat[lg][l], mat[lg][r - (1 << lg) + 1]); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); logs[0] = -1; for (int i = 1; i < max_N; ++i) { logs[i] = logs[i >> 1] + 1; } int N, K; std::cin >> N >> K; int M; std::cin >> M; std::vector<std::array<int, 2>> A(M); for (int i = 0; i < M; ++i) { std::cin >> A[i][0] >> A[i][1]; --A[i][0], --A[i][1]; } const int LG = logs[N]; std::vector<SparseTable> gost(LG); std::vector<std::vector<int>> go(LG, std::vector<int>(N)); { std::vector<std::vector<int>> mat(LG, std::vector<int>(N)); auto update = [&](int a, int b, int x) -> void { int d = b - a + 1; int lg = logs[d]; chmax(mat[lg][a], x); chmax(mat[lg][b - (1 << lg) + 1], x); }; for (int i = 0; i < M; ++i) { int a = A[i][0], b = A[i][1]; int l = a, r = std::min(b, a + K - 1); update(l, r, A[i][1]); } for(int l = LG - 1; l >= 1; --l) { int m = N - (1 << l) + 1; for (int i = 0; i < m; ++i) { chmax(mat[l - 1][i], mat[l][i]); chmax(mat[l - 1][i + (1 << (l - 1))], mat[l][i]); } } for (int i = 0; i < N; ++i) { go[0][i] = std::max(i, mat[0][i]); } } debug("hello"); for (int l = 0; l < LG; ++l) { debug(go[l]); gost[l].init(go[l]); if (l == LG - 1) { break; } for (int i = 0; i < N; ++i) { int x = go[l][i]; go[l + 1][i] = gost[l].get(i, x); } } debug("bro"); int Q; std::cin >> Q; while (Q--) { int S, T; std::cin >> S >> T; --S, --T; debug("?", S, T); if (S == T) { std::cout << "0\n"; continue; } int ans = 0, r = S; for (int l = LG - 1; l >= 0; --l) { int x = gost[l].get(S, r); debug(l, r, x); if (x < T) { r = std::max(r, x); ans += 1 << l; } } int x = gost[0].get(S, r); if (x < T) { std::cout << "-1\n"; } else { std::cout << ans + 1 << '\n'; } } return 0; }
#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...