Submission #1026483

#TimeUsernameProblemLanguageResultExecution timeMemory
1026483gygEvent Hopping (BOI22_events)C++17
10 / 100
1598 ms12372 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; 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()); } } 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 (r < lo || hi < l) return; if (l <= lo && hi <= r) { st[u] = min(st[u], x); return; } int mid = (lo + hi) / 2; update(l, r, x, 2 * u, lo, 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 (i < lo || hi < i) return INF; if (lo == hi) return st[u]; int mid = (lo + hi) / 2; return min({st[u], query(i, 2 * u, lo, mid), query(i, 2 * u + 1, mid + 1, hi)}); } array<int, MAX_N> dp; void comp(int f) { fill(st.begin(), st.end(), 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...