Submission #1263526

#TimeUsernameProblemLanguageResultExecution timeMemory
1263526altern23Event Hopping (BOI22_events)C++20
0 / 100
128 ms52824 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll, ll> #define fi first #define sec second #define ld long double const int MAXN = 2e5; const ll INF = 4e18; const int MOD = 998244353; ll S[MAXN + 5], E[MAXN + 5], lg[MAXN + 5], up[MAXN + 5][20]; pii sp[MAXN + 5][20]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; for(int i = 2; i <= MAXN; i++){ lg[i] = lg[i / 2] + 1; } for(;tc--;){ ll N, Q; cin >> N >> Q; vector<ll> comp; for(int i = 1; i <= N; i++){ cin >> S[i] >> E[i]; comp.push_back(S[i]), comp.push_back(E[i]); } sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); ll M = comp.size(); for(int i = 1; i <= M; i++) sp[i][0] = {INF, INF}; for(int i = 1; i <= N; i++){ S[i] = lower_bound(comp.begin(), comp.end(), S[i]) - comp.begin() + 1; E[i] = lower_bound(comp.begin(), comp.end(), E[i]) - comp.begin() + 1; sp[E[i]][0] = min(sp[E[i]][0], {S[i], i}); } for(int log = 1; log < 20; log++){ for(int i = 1; i <= M - (1LL << (log - 1)); i++) sp[i][log] = min(sp[i][log - 1], sp[i + (1LL << (log - 1))][log - 1]); } auto query = [&](ll l, ll r){ return min(sp[l][lg[r - l + 1]], sp[r - (1LL << lg[r - l + 1]) + 1][lg[r - l + 1]]); }; for(int i = 1; i <= N; i++){ up[i][0] = query(S[i], E[i]).sec; } for(int log = 1; log < 20; log++){ for(int i = 1; i <= N; i++){ up[i][log] = up[up[i][log - 1]][log - 1]; } } for(int i = 1; i <= Q; i++){ ll a, b; cin >> a >> b; if(a == b){ cout << 0 << "\n"; continue; } if(E[b] < E[a]){ cout << "impossible\n"; continue; } ll cur = b, dist = 0; bool ok = 0; for(int log = 19; log >= 0; --log){ if(S[up[cur][log]] > E[a]){ dist += (1LL << log); cur = up[cur][log]; } else{ ok = 1; } } if(!ok) cout << "impossible\n"; else cout << dist + 2 << "\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...