Submission #1015843

#TimeUsernameProblemLanguageResultExecution timeMemory
1015843asdfgraceEvent Hopping (BOI22_events)C++17
20 / 100
90 ms31296 KiB
#include <bits/stdc++.h> using namespace std; #define dbg(x) x #define prt(x) dbg(cerr << x) #define pv(x) dbg(cerr << #x << " = " << x << '\n') #define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n') #define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");) #define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << " "); prt("}\n");) #define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n')); #define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n')); /* sort by right bound out of everything with l[i] <= r[j] <= r[i] with leftmost left bound */ int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; vector<array<int, 2>> a(n); for (int i = 0; i < n; i++) { cin >> a[i][0] >> a[i][1]; } vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&] (int x, int y) { return a[x][1] < a[y][1] || (a[x][1] == a[y][1] && a[x][0] < a[y][0]); }); vector<int> at(n); for (int i = 0; i < n; i++) { at[ord[i]] = i; } sort(a.begin(), a.end(), [&] (array<int, 2> a1, array<int, 2> a2) { return a1[1] < a2[1] || (a1[1] == a2[1] && a1[0] < a2[0]); }); vector<int> l(n), r(n); for (int i = 0; i < n; i++) { l[i] = a[i][0]; r[i] = a[i][1]; } vector<vector<array<int, 2>>> rmq(20, vector<array<int, 2>>(n)); for (int i = 0; i < n; i++) { rmq[0][i] = {l[i], i}; } for (int j = 1; j < 20; j++) { for (int i = 0; i < n - (1 << (j - 1)); i++) { rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]); } } function<array<int, 2>(int, int)> mnq = [&] (int lb, int rb) { int len = rb - lb + 1, mxbit = 31 - __builtin_clz(len); return min(rmq[mxbit][lb], rmq[mxbit][rb - (1 << mxbit) + 1]); }; vector<int> to(n); for (int i = 0; i < n; i++) { int lb = lower_bound(r.begin(), r.end(), l[i]) - r.begin(); int rb = upper_bound(r.begin(), r.end(), r[i]) - r.begin() - 1; array<int, 2> best = mnq(lb, rb); to[i] = best[1]; } vector<vector<int>> lift(20, vector<int>(n, 0)); lift[0] = to; for (int j = 1; j < 20; j++) { for (int i = 0; i < n; i++) { lift[j][i] = lift[j - 1][lift[j - 1][i]]; } } while (q--) { int st, en; cin >> st >> en; st--; en--; st = at[st]; en = at[en]; if (r[en] < r[st]) { cout << "impossible\n"; continue; } else if (st == en) { cout << 0 << '\n'; continue; } int ans = 0; for (int bit = 19; bit >= 0; bit--) { if (r[lift[bit][en]] > r[st]) { ans += 1 << bit; en = lift[bit][en]; } } if (l[en] > r[st]) { cout << "impossible\n"; } else { cout << ans + 1 << '\n'; } } } /* any observations help check every line IF YOUR LINES AREN'T WRONG CHECK IF YOUR LINES ARE IN THE RIGHT ORDER NEVER GIVE UP */
#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...