제출 #1072075

#제출 시각아이디문제언어결과실행 시간메모리
1072075duckindogEvent Hopping (BOI22_events)C++17
40 / 100
1598 ms30160 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, q; struct Event { int st, ed, idx; } a[N]; int rvs[N]; int lg[N]; int pre[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> a[i].st >> a[i].ed, a[i].idx = i; sort(a + 1, a + n + 1, [&](const auto& a, const auto& b) { return a.ed < b.ed; }); for (int i = 1; i <= n; ++i) rvs[a[i].idx] = i; for (int i = 2; i < N; ++i) lg[i] = lg[i >> 1] + 1; { //init vector<int> rrh; for (int i = 1; i <= n; ++i) { rrh.push_back(a[i].st); rrh.push_back(a[i].ed); } sort(rrh.begin(), rrh.end()); rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end()); a[0] = {1'000'000, 1'000'000}; vector<vector<int>> save(rrh.size() + 1); for (int i = 1; i <= n; ++i) { a[i].st = upper_bound(rrh.begin(), rrh.end(), a[i].st) - rrh.begin(); a[i].ed = upper_bound(rrh.begin(), rrh.end(), a[i].ed) - rrh.begin(); save[a[i].ed].push_back(i); } vector<array<int, 19>> f(rrh.size() + 1); using pii = pair<int, int>; priority_queue<pii, vector<pii>, greater<>> q; for (int i = 1; i <= rrh.size(); ++i) { for (const auto& idx : save[i]) q.push({a[idx].st, idx}); while (q.size() && a[q.top().second].ed < i) q.pop(); f[i][0] = (!q.size() ? 0 : q.top().second); } for (int j = 1; j <= 18; ++j) { for (int i = 1; i + (1 << j) - 1 <= rrh.size(); ++i) { int lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1]; f[i][j] = (a[lt].st < a[rt].st ? lt : rt); } } auto get = [&](int l, int r) { int j = lg[r - l + 1]; int lt = f[l][j], rt = f[r - (1 << j) + 1][j]; return a[lt].st < a[rt].st ? lt : rt; }; for (int i = 1; i <= n; ++i) pre[i] = get(a[i].st, a[i].ed); } auto in = [&](int x, int y) { return a[y].st <= a[x].ed && a[x].ed <= a[y].ed; }; while (q--) { int x, y; cin >> x >> y; x = rvs[x]; y = rvs[y]; if (in(x, y)) { cout << 1 - (x == y) << "\n"; continue; } if (a[x].st >= a[y].ed) { cout << "impossible\n"; continue; } int answer = 0; while (!in(x, y) && y != pre[y]) { y = pre[y]; answer += 1; } if (!in(x, y)) { cout << "impossible\n"; continue; } cout << answer + (x != y) << "\n"; } }

컴파일 시 표준 에러 (stderr) 메시지

events.cpp: In function 'int32_t main()':
events.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 1; i <= rrh.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
events.cpp:52:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for (int i = 1; i + (1 << j) - 1 <= rrh.size(); ++i) {
      |                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
events.cpp:53:50: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |         int lt = f[i][j - 1], rt = f[i + (1 << j - 1)][j - 1];
      |                                                ~~^~~
#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...