제출 #986061

#제출 시각아이디문제언어결과실행 시간메모리
986061KLKLKRailway Trip 2 (JOI22_ho_t4)C++17
100 / 100
309 ms52396 KiB
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <set> #define PI pair<int, int> using namespace std; struct SegmentTree { int n; vector<PI> data; void combine(int v) { data[v].first = min(data[v << 1].first, data[v << 1 | 1].first); data[v].second = max(data[v << 1].second, data[v << 1 | 1].second); } SegmentTree(int n) : n(n), data(vector<PI>(n << 1, {INT32_MAX, INT32_MIN})) { } void build(int l, const vector<PI> &I) { for (int i = 1; i <= l; ++i) data[n + i] = I[i]; for (int v = n - 1; v; --v) combine(v); } PI query(int l, int r) { l += n; r += n; PI ans = {INT32_MAX, INT32_MIN}; while (l < r) { if (l & 1) { ans = {min(ans.first, data[l].first), max(ans.second, data[l].second)}; l++; } if (r & 1) { --r; ans = {min(ans.first, data[r].first), max(ans.second, data[r].second)}; } l >>= 1; r >>= 1; } return ans; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, q, k; cin >> n >> k >> m; vector<PI> forward; vector<PI> backward; int a, b; for (int i = 0; i < m; ++i) { cin >> a >> b; if (a < b) { forward.emplace_back(a, b); forward.emplace_back(min(a + k, b), -b); } else { backward.emplace_back(a, b); backward.emplace_back(max(a - k, b), -b); } } multiset<int> ends; vector<PI> I(n + 1); sort(forward.begin(), forward.end()); sort(backward.begin(), backward.end(), greater<>()); auto itr = forward.begin(); for (int i = 1; i <= n; ++i) { while (itr != forward.end() && itr->first == i) { if (itr->second > 0) ends.insert(itr->second); else ends.erase(ends.find(-itr->second)); ++itr; } if (!ends.empty()) I[i].second = *ends.rbegin(); else I[i].second = i; } itr = backward.begin(); for (int i = n; i; --i) { while (itr != backward.end() && itr->first == i) { if (itr->second > 0) ends.insert(itr->second); else ends.erase(ends.find(-itr->second)); ++itr; } if (!ends.empty()) I[i].first = *ends.begin(); else I[i].first = i; } vector<SegmentTree> interval(20, SegmentTree(1 << 17)); interval[0].build(n, I); for (int j = 1; j < 20; ++j) { for (int i = 1; i <= n; ++i) { I[i] = interval[j - 1].query(I[i].first, I[i].second + 1); } interval[j].build(n, I); } cin >> q; while (q--) { cin >> a >> b; if (b < interval[19].query(a, a + 1).first || b > interval[19].query(a, a + 1).second) cout << "-1\n"; else { int res = 1; int l = a; int r = a; for (int j = 19; j >= 0; -- j) { PI qry = interval[j].query(l, r + 1); if (b < qry.first || b > qry.second) { res += 1 << j; l = qry.first; r = qry.second; } } 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...