Submission #1026490

#TimeUsernameProblemLanguageResultExecution timeMemory
1026490gygEvent Hopping (BOI22_events)C++17
0 / 100
80 ms25904 KiB
#pragma GCC optimize("O3", "unroll-loops") #pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int MAX_N = 1e5 + 5, INF = 1e9; int n, q; array<int, MAX_N> l, r; vector<pii> ord; // {r, i} int n_ccs; unordered_map<int, int> cc; array<int, MAX_N> cc_l, cc_r; void precomp() { for (int i = 1; i <= n; i++) ord.push_back({r[i], i}); sort(ord.rbegin(), ord.rend()); set<int> coords; for (int i = 1; i <= n; i++) coords.insert(l[i]), coords.insert(r[i]); while (coords.size()) { n_ccs++, cc[*coords.begin()] = n_ccs; coords.erase(coords.begin()); } for (int i = 1; i <= n; i++) cc_l[i] = cc[l[i]], cc_r[i] = cc[r[i]]; } array<int, 8 * MAX_N> st; void update(int l, int r, int x, int u = 1, int lo = 1, int hi = n_ccs) { if (l <= lo && hi <= r) { st[u] = min(st[u], x); return; } int mid = (lo + hi) / 2; if (l <= mid) update(l, r, x, 2 * u, lo, mid); if (r > mid) update(l, r, x, 2 * u + 1, mid + 1, hi); } int query(int i, int u = 1, int lo = 1, int hi = n_ccs) { if (lo == hi) return st[u]; int mid = (lo + hi) / 2; if (i <= mid) return min(st[u], query(i, 2 * u, lo, mid)); else return min(st[u], query(i, 2 * u + 1, mid + 1, hi)); } array<int, MAX_N> dp; void comp(int f) { fill(st.begin() + 1, st.end() + 4 * n_ccs, INF); for (pii x : ord) { int i = x.second; if (i == f) dp[i] = 0; else if (l[f] <= r[i] && r[i] <= r[f]) dp[i] = 1; else dp[i] = query(cc_r[i]) + 1; update(cc_l[i], cc_r[i], dp[i]); } } int main() { // freopen("event.in", "r", stdin); cin.sync_with_stdio(false), cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> l[i] >> r[i]; precomp(); for (int i = 1; i <= q; i++) { int s, f; cin >> s >> f; comp(f); if (dp[s] >= INF) cout << "impossible" << '\n'; else cout << dp[s] << '\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...