Submission #727868

#TimeUsernameProblemLanguageResultExecution timeMemory
727868Charizard2021Event Hopping (BOI22_events)C++17
100 / 100
369 ms26192 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<vector<int> > dp(17, vector<int>(n)); vector<vector<pair<int, int> > > sparseTables(17, vector<pair<int, int> >(n, make_pair(1000000001, -1))); vector<pair<int, int> > a(n); vector<int> b; for (int i = 0; i < n; i++) { cin >> a[i].first >> a[i].second; b.push_back(a[i].second); } sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); for (int i = 0; i < n; i++) { int right = lower_bound(b.begin(), b.end(), a[i].second) - b.begin(); sparseTables[0][right] = min(sparseTables[0][right], make_pair(a[i].first, i)); } for (int i = 0; i + 1 < 17; i++){ for (int j = 0; j + (1 << (i + 1)) <= n; j++){ sparseTables[i + 1][j] = min(sparseTables[i][j], sparseTables[i][j + (1 << i)]); } } for (int i = 0; i < n; i++){ int left = lower_bound(b.begin(), b.end(), a[i].first) - b.begin(); int right = lower_bound(b.begin(), b.end(), a[i].second) - b.begin(); int h = 31 - __builtin_clz(right - left + 1); dp[0][i] = min(sparseTables[h][left], sparseTables[h][right + 1 - (1 << h)]).second; } for (int i = 0; i + 1 < 17; i++){ for (int j = 0; j < n; j++){ dp[i + 1][j] = dp[i][dp[i][j]]; } } while (q--) { int x, y; int left = 1; cin >> x >> y; x--; y--; if (x == y || (a[y].first <= a[x].second && a[x].second <= a[y].second)) { cout << (x == y ? 0 : 1) << "\n"; continue; } for (int i = 17 - 1; ~i; i--) { if (a[x].second < a[dp[i][y]].first){ left += 1 << i, y = dp[i][y]; } } y = dp[0][y]; if (a[x].second < a[y].first || a[x].second > a[y].second){ cout << "impossible\n"; } else{ cout << left + (a[x].second >= a[y].first) << "\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...