Submission #1217643

#TimeUsernameProblemLanguageResultExecution timeMemory
1217643trimkusRailway Trip 2 (JOI22_ho_t4)C++20
60 / 100
1296 ms128200 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); } 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_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); } 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); } void setval(int i, int l, int r, int qp, int val) { if (l == r) { tree[i] = val; return; } int m = (l + r) / 2; if (qp <= m) setval(i * 2, l, m, qp, val); else setval(i * 2 + 1, m + 1, r, qp, val); tree[i] = max(tree[i * 2], tree[i * 2 + 1]); } void setval(int qp, int val) { setval(1, 1, n, qp, val); } }; 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); } }; 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; //~ assert(a < b); int res = -1; if (a < b) { int nxt = a; int now = 0; for (int i = LOG; i >= 0; --i) { int NEXT = lifts[i].query_max(a, nxt); //~ cerr << a << " -> " << nxt << "\n"; if (NEXT > nxt && NEXT < b) { nxt = NEXT; now += (1 << i); } } now += 1; a = lifts[0].query_max(a, nxt); //~ cerr << a << " " << b << " = "; if (a >= b) { res = now; } } else { int nxt = a; int now = 0; //~ cerr << "Query start = " << nxt << " " << a << " to " << b << "\n"; for (int i = LOG; i >= 0; --i) { int NEXT = rlifts[i].query_min(nxt, a); //~ cerr << nxt << " -> " << a << "\n"; if (NEXT < nxt && NEXT > b) { nxt = NEXT; now += (1 << i); } } now += 1; a = rlifts[0].query_min(nxt, a); //~ cerr << a << " " << b << " = "; if (a <= b) { res = now; } } cout << res << "\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...