Submission #588979

#TimeUsernameProblemLanguageResultExecution timeMemory
588979ParsaEsEvent Hopping (BOI22_events)C++14
50 / 100
1519 ms6272 KiB
//InTheNameOfGOD //PRS;) #pragma GCC optimize("unroll-loops", "Ofast", "O3") #include<bits/stdc++.h> #define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, l, r) for(ll i = l; i < r; i++) #define min(x, y) (x < y ? x : y) #define max(x, y) (x > y ? x : y) #define X first #define Y second typedef int ll; using namespace std; typedef pair<ll, ll> pl; typedef pair<ll, pl> pi; constexpr ll inf = 2e9, xn = 1e5 + 5, s = 317; ll d[xn], p[xn], sx[xn], x[xn], m[s]; pi e[xn]; int main() { Fast ll n, q; cin >> n >> q; rep(i, 0, n) cin >> e[i].Y.X >> e[i].X; rep(i, 0, n) e[i] = {-e[i].X, {-e[i].Y.X, i}}; sort(e, e + n); rep(i, 0, s) m[i] = -inf; rep(i, 0, n) { sx[i] = x[i] = -1; rep(j, 0, i / s + 1) if(e[i].X <= m[j]) { rep(k, j * s, min((j + 1) * s, i)) if(e[i].X <= e[k].Y.X) { if(k / s < i / s) sx[i] = k, d[i] = 1; else if(sx[k] >= 0) sx[i] = sx[k], d[i] = d[k] + 1; x[i] = k; break; } break; } m[i / s] = max(e[i].Y.X, m[i / s]), p[e[i].Y.Y] = i; } while(q--) { ll l, r, ans = 0; cin >> l >> r; if(l == r) { cout << "0\n"; continue; } l = p[l - 1], r = p[r - 1]; if(e[l].X < e[r].X) { cout << "impossible\n"; continue; } if(e[l].X == e[r].X) { cout << "1\n"; continue; } while(sx[l] >= r) ans += d[l], l = sx[l]; while(x[l] >= r) l = x[l], ans++; if(r == l) { cout << ans << '\n'; continue; } if(e[r].X == e[l].X) { cout << ans + 1 << '\n'; continue; } ll z = e[r].Y.X, mx = e[r].Y.X; bool f = 1; rep(i, r + 1, l + 1) { if(z < e[i].X && mx < e[i].X) { f = 0; break; } if(z < e[i].X) z = mx, ans++; mx = max(mx, e[i].Y.X); } if(f) cout << ans + 1 << '\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...