Submission #1217669

#TimeUsernameProblemLanguageResultExecution timeMemory
1217669trimkusRailway Trip 2 (JOI22_ho_t4)C++20
16 / 100
2099 ms125384 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = double; const int LOG = 21; const int MAXM = 1e5; int lift[MAXM + 1][LOG + 2]; struct RMQ { vector<int> tree; int n; void init(int n, int val) { this->n = n; tree = vector<int>(4 * n, val); } void update_max(int i, int l, int r, int qp, int val) { if (l == r) { tree[i] = max(tree[i], val); return; } int m = (l + r) / 2; if (qp <= m) update_max(i * 2, l, m, qp, val); else update_max(i * 2 + 1, m + 1, r, qp, val); tree[i] = max(tree[i * 2], tree[i * 2 + 1]); } void update_max(int qp, int val) { update_max(1, 1, n, qp, val); } int query_max(int i, int l, int r, int ql, int qr) { if (l > qr || r < ql) return -1; if (ql <= l && r <= qr) return tree[i]; int m = (l + r) / 2; return max(query_max(i * 2, l, m, ql, qr), query_max(i * 2 + 1, m + 1, r, ql, qr)); } int query_max(int ql, int qr) { return query_max(1, 1, n, ql, qr); } }; struct RMQ_MIN { vector<int> tree; int n; void init(int n, int val) { this->n = n; tree = vector<int>(4 * n, val); } void update_min(int i, int l, int r, int qp, int val) { if (l == r) { tree[i] = min(tree[i], val); return; } int m = (l + r) / 2; if (qp <= m) update_min(i * 2, l, m, qp, val); else update_min(i * 2 + 1, m + 1, r, qp, val); tree[i] = min(tree[i * 2], tree[i * 2 + 1]); } void update_min(int qp, int val) { update_min(1, 1, n, qp, val); } int query_min(int i, int l, int r, int ql, int qr) { if (l > qr || r < ql) return n + 1; if (ql <= l && r <= qr) return tree[i]; int m = (l + r) / 2; return min(query_min(i * 2, l, m, ql, qr), query_min(i * 2 + 1, m + 1, r, ql, qr)); } int query_min(int ql, int qr) { return query_min(1, 1, n, ql, qr); } }; struct LazySeg { }; int main() { //~ ofstream cout("out.txt"); ios::sync_with_stdio(0); cin.tie(0); int n, k, m; cin >> n >> k >> m; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= LOG; ++j) { lift[i][j] = -1; } } vector<vector<array<int, 2>>> events(n + 1), revents(n + 1); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; if (a < b) { int till = min(b, a + k); events[a].push_back({b, till}); events[till].push_back({-b, till}); } else { a = n - a + 1; b = n - b + 1; int till = min(b, a + k); assert(a < till); assert(a > 0); assert(b <= n); revents[a].push_back({b, till}); revents[till].push_back({-b, till}); } } vector<RMQ> lifts(LOG + 1), nrlifts(LOG + 1); vector<RMQ_MIN> rlifts(LOG + 1); { multiset<pair<int, int>> mt; for (int j = 1; j <= n; ++j) { for (auto& u : events[j]) { if (u[0] < 0) { mt.erase(mt.find({-u[0], u[1]})); } else { mt.insert({u[0], u[1]}); } } if (mt.size() > 0) { auto it = prev(mt.end()); lift[j][0] = it->first; } } for (int i = 0; i <= LOG; ++i) { lifts[i].init(n, -1); for (int j = 1; j <= n; ++j) { lifts[i].update_max(j, lift[j][i]); } for (int j = 1; j <= n; ++j) { lift[j][i + 1] = lifts[i].query_max(j, lift[j][i]); } } } { for (int i = 0; i <= n; ++i) { for (int j = 0; j <= LOG; ++j) { lift[i][j] = -1; } } multiset<pair<int, int>> mt; for (int j = 1; j <= n; ++j) { for (auto& u : revents[j]) { if (u[0] < 0) { mt.erase(mt.find({-u[0], u[1]})); } else { mt.insert({u[0], u[1]}); } } if (mt.size() > 0) { auto it = prev(mt.end()); lift[j][0] = it->first; } } for (int i = 0; i <= LOG; ++i) { nrlifts[i].init(n, -1); for (int j = 1; j <= n; ++j) { nrlifts[i].update_max(j, lift[j][i]); } for (int j = 1; j <= n; ++j) { lift[j][i + 1] = nrlifts[i].query_max(j, lift[j][i]); } } for (int j = 0; j <= LOG; ++j) { rlifts[j].init(n, n); vector<int> vals; for (int i = 1; i <= n; ++i) { int val = nrlifts[j].query_max(i, i); vals.push_back(val); } reverse(begin(vals), end(vals)); for (int i = 1; i <= n; ++i) { if (vals[i - 1] != -1) { vals[i - 1] = n - vals[i - 1] + 1; } else { vals[i - 1] = n + 1; } rlifts[j].update_min(i, vals[i - 1]); } } } int q; cin >> q; while (q--) { int a, b; cin >> a >> b; queue<array<int, 3>> q; vector<bool> vis(n + 1); vector<int> dist(n + 1, -1); dist[a] = 0; vis[a] = true; q.push({a, a, 0}); while (q.size()) { int layer = q.size(); while (layer--) { int v1 = q.front()[0]; int v2 = q.front()[1]; int d = q.front()[2]; //~ cout << v << " "; q.pop(); int right = max(v2, lifts[0].query_max(v1, v2)); int left = min(v1, rlifts[0].query_min(v1, v2)); if (v1 == left && right == v2) continue; for (int i = left; i <= right; ++i) { if (dist[i] == -1) { dist[i] = d + 1; } } if (right != -1 && !vis[right]) { vis[right] = 1; q.push({v1, right, d + 1}); } if (left != -1 && !vis[left]) { vis[left] = 1; q.push({left, v2, d + 1}); } } } //~ for (int i = 1; i <= n; ++i) { //~ if (dist[i] == -1) cout << "- "; //~ else cout << dist[i] << " "; //~ } //~ cout << "\n"; cout << dist[b] << "\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...