Submission #1274646

#TimeUsernameProblemLanguageResultExecution timeMemory
1274646MisterReaperRailway Trip 2 (JOI22_ho_t4)C++20
35 / 100
222 ms224964 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; } template<typename T> bool chmin(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 Pair { int l, r; Pair() {} Pair(int x) : l(x), r(x) {} Pair(int x, int y) : l(x), r(y) {} }; Pair operator+ (const Pair& lhs, const Pair& rhs) { Pair res; res.l = std::min(lhs.l, rhs.l); res.r = std::max(lhs.r, rhs.r); return res; } struct SparseTable { int n; std::vector<std::vector<Pair>> mat; SparseTable() {} void init(std::vector<Pair>& 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] = mat[i - 1][j] + mat[i - 1][j + (1 << (i - 1))]; } } } Pair get(int l, int r) { int d = r - l + 1; int lg = logs[d]; return 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] + 1; std::vector<SparseTable> gost(LG); std::vector<std::vector<Pair>> go(LG, std::vector<Pair>(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].r = std::max(i, mat[0][i]); } } { std::vector<std::vector<int>> mat(LG, std::vector<int>(N, N)); auto update = [&](int a, int b, int x) -> void { int d = b - a + 1; int lg = logs[d]; chmin(mat[lg][a], x); chmin(mat[lg][b - (1 << lg) + 1], x); }; for (int i = 0; i < M; ++i) { int a = A[i][0], b = A[i][1]; if (a > b) { int l = std::max(b, a - K + 1), r = a; 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) { chmin(mat[l - 1][i], mat[l][i]); chmin(mat[l - 1][i + (1 << (l - 1))], mat[l][i]); } } for (int i = 0; i < N; ++i) { go[0][i].l = std::min(i, mat[0][i]); } } debug("hello"); for (int l = 0; l < LG; ++l) { gost[l].init(go[l]); if (l == LG - 1) { break; } for (int i = 0; i < N; ++i) { auto rng = go[l][i]; go[l + 1][i] = gost[l].get(rng.l, rng.r); } } debug("bro"); int Q; std::cin >> Q; while (Q--) { int S, T; std::cin >> S >> T; --S, --T; debug("?", S, T); int ans = 0; Pair rng = S; for (int l = LG - 1; l >= 0; --l) { Pair x = gost[l].get(rng.l, rng.r); if (!(x.l <= T && T <= x.r)) { ans += 1 << l; rng = x; } } Pair x = gost[0].get(rng.l, rng.r); if (!(x.l <= T && T <= x.r)) { 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...