Submission #1190442

#TimeUsernameProblemLanguageResultExecution timeMemory
1190442anmattroiEvent Hopping (BOI22_events)C++17
0 / 100
254 ms63592 KiB
#include <bits/stdc++.h> #define maxn 100005 #define fi first #define se second using namespace std; using ii = pair<int, int>; int n, q; int f[20][maxn]; ii a[maxn]; int c[2*maxn], n1 = 0; ii lz[8*maxn], st[8*maxn]; void apply(int r, ii d) { lz[r] = max(lz[r], d); st[r] = max(st[r], d); } void down(int r) { apply(r<<1, lz[r]); apply(r<<1|1, lz[r]); } void up(int r) { st[r] = max(st[r<<1], st[r<<1|1]); } void update(int u, int v, ii d, int r = 1, int lo = 1, int hi = n1) { if (u <= lo && hi <= v) { apply(r, d); return; } down(r); int mid = (lo + hi) >> 1; if (u <= mid) update(u, v, d, r<<1, lo, mid); if (v > mid) update(u, v, d, r<<1|1, mid+1, hi); up(r); } ii get(int u, int v, int r = 1, int lo = 1, int hi = n1) { if (u <= lo && hi <= v) return st[r]; int mid = (lo + hi) >> 1; down(r); return max(u <= mid ? get(u, v, r<<1, lo, mid) : ii{0, 0}, v > mid ? get(u, v, r<<1|1, mid+1, hi) : ii{0, 0}); } int it[48*maxn], L[48*maxn], R[48*maxn], nt = 0; int root[maxn]; vector<ii> adj[maxn]; int build(int lo = 1, int hi = n1) { if (lo == hi) return ++nt; int cur = ++nt, mid = (lo + hi) >> 1; L[cur] = build(lo, mid); R[cur] = build(mid+1, hi); return cur; } int updPst(int u, int d, int oldver, int lo = 1, int hi = n1) { if (lo == hi) { it[++nt] = it[oldver] + d; return nt; } int cur = ++nt, mid = (lo + hi) >> 1; if (u <= mid) { L[cur] = updPst(u, d, L[oldver], lo, mid); R[cur] = R[oldver]; } else { L[cur] = L[oldver]; R[cur] = updPst(u, d, R[oldver], mid+1, hi); } it[cur] = it[L[cur]] + it[R[cur]]; return cur; } int getPst(int u, int v, int r, int lo = 1, int hi = n1) { if (u <= lo && hi <= v) return it[r]; int mid = (lo + hi) >> 1; return (u <= mid ? getPst(u, v, L[r], lo, mid) : 0) + (v > mid ? getPst(u, v, R[r], mid+1, hi) : 0); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se; for (int i = 1; i <= n; i++) { c[++n1] = a[i].fi; c[++n1] = a[i].se; } sort(c + 1, c + n1 + 1); n1 = unique(c + 1, c + n1 + 1) - c - 1; root[0] = build(); for (int i = 1; i <= n; i++) { int p = lower_bound(c + 1, c + n1 + 1, a[i].fi) - c, q = lower_bound(c + 1, c + n1 + 1, a[i].se) - c; adj[p].emplace_back(q, 1); adj[q+1].emplace_back(q, -1); update(p, q, ii{a[i].se, i}); } for (int i = 1; i <= n1; i++) { root[i] = root[i-1]; for (auto [v, p] : adj[i]) root[i] = updPst(v, p, root[i]); } for (int i = 1; i <= n; i++) { int p = lower_bound(c + 1, c + n1 + 1, a[i].fi) - c, q = lower_bound(c + 1, c + n1 + 1, a[i].se) - c; ii o = get(p, q); if (o.fi == a[i].se) f[0][i] = i; else f[0][i] = o.se; } for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++) f[i][j] = f[i-1][f[i-1][j]]; while (q--) { int s, e; cin >> s >> e; if (s == e) { cout << "0\n"; continue; } auto [u, v] = a[e]; int ans = 0; for (int i = 19; i >= 0; i--) if (a[f[i][s]].se < u) { ans += (1<<i); s = f[i][s]; } if (u <= a[s].se && a[s].se <= v) { cout << ++ans << "\n"; continue; } int p = lower_bound(c + 1, c + n1 + 1, a[s].se) - c; int A = lower_bound(c + 1, c + n1 + 1, u) - c, B = lower_bound(c + 1, c + n1 + 1, v) - c; if (getPst(A, B, root[p])) cout << (ans += 2) << "\n"; else cout << "impossible\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...