Submission #584395

#TimeUsernameProblemLanguageResultExecution timeMemory
584395alireza_kavianiEvent Hopping (BOI22_events)C++17
100 / 100
141 ms13616 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define all(x) (x).begin(),(x).end() #define X first #define Y second #define sep ' ' #define endl '\n' #define SZ(x) ll(x.size()) const ll MAXN = 1e6 + 10; const ll LOG = 22; const ll INF = 8e18; const ll MOD = 1e9 + 7; //998244353; //1e9 + 9; int n , q , S[MAXN] , E[MAXN] , nxt[LOG][MAXN]; vector<pair<pii , int>> stk; vector<int> vec; int cmp(int x , int y){ if(E[x] != E[y]) return E[x] < E[y]; return S[x] < S[y]; } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> q; for(int i = 1 ; i <= n ; i++){ cin >> S[i] >> E[i]; vec.push_back(i); } sort(all(vec) , cmp); for(auto& i : vec){ while(SZ(stk) && S[i] <= stk.back().X.Y){ stk.pop_back(); } stk.push_back({{E[i] , S[i]} , i}); nxt[0][i] = lower_bound(all(stk) , pair<pii , int>({{S[i] , -MOD} , -MOD})) -> Y; //cout << i << sep << nxt[0][i] << endl; } for(int i = 1 ; i < LOG ; i++){ for(int j = 1 ; j <= n ; j++){ nxt[i][j] = nxt[i - 1][nxt[i - 1][j]]; } } while(q--){ int v , u; cin >> v >> u; if(E[u] < E[v]){ cout << "impossible" << endl; continue; } if(v == u){ cout << 0 << endl; continue; } if(S[u] <= E[v]){ cout << 1 << endl; continue; } int ans = 0; for(int i = LOG - 1 ; i >= 0 ; i--){ if(S[nxt[i][u]] > E[v]){ u = nxt[i][u]; ans += (1 << i); } } if(E[v] < S[nxt[0][u]]){ cout << "impossible" << endl; continue; } cout << ans + 2 << endl; } return 0; } /* */
#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...