Submission #1217673

#TimeUsernameProblemLanguageResultExecution timeMemory
1217673trimkusRailway Trip 2 (JOI22_ho_t4)C++20
0 / 100
2100 ms128500 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 { vector<int> tree; vector<int> lz; int n; LazySeg(int n) { this->n = n; tree = vector<int>(4 * n, 2 * n + 1); lz = vector<int>(4 * n, 2 * n + 1); } void push(int i) { if (lz[i] != -1) { for (int v : {2 * i, 2 * i + 1}) { if (tree[v] == -1) tree[v] = lz[i]; if (lz[v] == -1) lz[v] = lz[i]; tree[v] = min(tree[v], lz[i]); lz[v] = min(lz[v], lz[i]); } lz[i] = -1; } } void update(int i, int l, int r, int ql, int qr, int val) { if (l > qr || r < ql) return; if (ql <= l && r <= qr) { if (tree[i] == -1) tree[i] = val; if (lz[i] == -1) lz[i] = val; tree[i] = min(tree[i], val); lz[i] = min(lz[i], val); return; } push(i); int m = (l + r) / 2; update(i * 2, l, m, ql, qr, val); update(i * 2 + 1, m + 1, r, ql, qr, val); tree[i] = min(tree[i * 2], tree[i * 2 + 1]); } void update(int ql, int qr, int val) { update(1, 1, n, ql, qr, val); } int query(int i, int l, int r, int qp) { if (l == r) { return tree[i]; } push(i); int m = (l + r) / 2; if (qp <= m) return query(i * 2, l, m, qp); return query(i * 2 + 1, m + 1, r, qp); } }; 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; LazySeg lz(n); 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; //~ } //~ } lz.update(left, right, 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"; int res = lz.query(1, 1, n, n); if (res > 2 * n) { cout << "-1\n"; } else { cout << res << "\n"; } //~ cout << lz.query(1, 1, n, 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...