Submission #941161

#TimeUsernameProblemLanguageResultExecution timeMemory
941161peterandvoiRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
251 ms262100 KiB
#include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif const int N = (int) 1e5 + 5; const int LOG = 18; int n, k, m, q; int lg[N]; pair<int, int> st[LOG][N]; int a[N << 1], b[N << 1]; vector<int> in[N], out[N]; struct sparse_table { pair<int, int> spt[LOG - 1][N]; pair<int, int> cmb(pair<int, int> a, pair<int, int> b) { return {min(a.first, b.first), max(a.second, b.second)}; } void build(int j) { for (int i = 1; i <= n; ++i) { spt[0][i] = st[j][i]; } for (int j = 1; j <= lg[n]; ++j) { for (int i = 1; i + (1 << j) - 1 <= n; ++i) { spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << (j - 1))]); } } } pair<int, int> get(int l, int r) { int k = lg[r - l + 1]; return cmb(spt[k][l], spt[k][r - (1 << k) + 1]); } } spt[LOG]; signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef ngu freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif cin >> n >> k >> m; vector<int> inc, dec; for (int i = 1; i <= m; ++i) { cin >> a[i] >> b[i]; (a[i] < b[i] ? inc : dec).emplace_back(i); } for (int i : inc) { in[a[i]].emplace_back(b[i]); out[min(b[i] - 1, a[i] + k - 1)].emplace_back(b[i]); } multiset<int> s; for (int i = 1; i <= n; ++i) { if (i > 1) { lg[i] = lg[i / 2] + 1; } st[0][i] = {i, i}; for (int r : in[i]) { s.insert(r); } if (s.size()) { st[0][i].second = *s.rbegin(); } for (int r : out[i]) { s.erase(s.find(r)); } in[i].clear(); out[i].clear(); } s.clear(); for (int i : dec) { in[a[i]].emplace_back(b[i]); out[max(b[i] + 1, a[i] - k + 1)].emplace_back(b[i]); } for (int i = n; i >= 1; --i) { for (int l : in[i]) { s.insert(l); } if (s.size()) { st[0][i].first = *s.begin(); } for (int l : out[i]) { s.erase(s.find(l)); } } spt[0].build(0); for (int j = 1; j < LOG; ++j) { for (int i = 1; i <= n; ++i) { st[j][i] = spt[j - 1].get(st[j - 1][i].first, st[j - 1][i].second); } spt[j].build(j); } auto reach = [&](pair<int, int> x, int i) -> bool { return x.first <= i && i <= x.second; }; cin >> q; while (q--) { int s, t; cin >> s >> t; if (reach(st[LOG - 1][s], t)) { pair<int, int> cur = {s, s}; int res = 0; for (int i = LOG - 2; i >= 0; --i) { pair<int, int> new_cur = spt[i].get(cur.first, cur.second); if (!reach(new_cur, t)) { cur = new_cur; res += 1 << i; } } cout << res + 1 << "\n"; } else { cout << -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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...