제출 #750512

#제출 시각아이디문제언어결과실행 시간메모리
750512vjudge1Event Hopping (BOI22_events)C++17
25 / 100
354 ms33612 KiB
#include<bits/stdc++.h> using namespace std; const int INF = 1e9; const int N = 1e5 + 5; const int LOG = 20; pair<int , int> seg[N << 2]; map<int , int> mp , mpp; vector<pair<int , int> > vp; vector<int> vec; int dp[N][LOG] , s[N] , e[N] , num , n , q; void compress(){ // sort(vec.begin() , vec.end()); // mp[vec[0]] = num; // for(int i = 1 ; i < (int)vec.size() ; i++){ // if(vec[i] == vec[i - 1]) continue; // mp[vec[i]] = ++num; // } // for(int i = 1 ; i <= n ; i++){ // s[i] = mp[s[i]]; // e[i] = mp[e[i]]; // } for(int i = 1 ; i <= n ; i++){ mp[s[i]] = 1; mp[e[i]] = 1; } for(auto i : mp) mpp[i.first] = ++num; for(int i = 1 ; i <= n ; i++){ s[i] = mpp[s[i]]; e[i] = mpp[e[i]]; // cout << "aga " << s[i] << ' ' << e[i] << '\n'; } } void clr(){ for(int i = 0 ; i < (N << 2) ; i++) seg[i] = {INF , INF}; } void update(int ver , int left , int right , int ind , int st , int ed){ if(ed < left || right <= ed) return; if(left + 1 == right){ if(seg[ver].first > st) seg[ver] = {st , ind}; return; } int mid = (right + left) >> 1; update(ver << 1 , left , mid , ind , st , ed); update(ver << 1 | 1 , mid , right , ind , st , ed); if(seg[ver << 1].first > seg[ver << 1 | 1].first) seg[ver] = seg[ver << 1 | 1]; else seg[ver] = seg[ver << 1]; } pair<int , int> get(int ver , int left , int right , int l , int r){ if(left >= r || right <= l) return {INF , INF}; if(left >= l && right <= r) return seg[ver]; int mid = (right + left) >> 1; pair<int , int> ans1 = get(ver << 1 , left , mid , l , r); pair<int , int> ans2 = get(ver << 1 | 1 , mid , right , l , r); if(ans1.first > ans2.first) return ans2; else return ans1; } void cal(){ for(int i = 1 ; i <= n ; i++) update(1 , 1 , N , i , s[i] , e[i]); for(int i = 1 ; i <= n ; i++){ vp.push_back(get(1 , 1 , N , s[i] , e[i] + 1)); // cout << i << ": " << vp.back().first << ' ' << vp.back().second << '\n'; } } void find_dp(){ for(int i = 1 ; i <= n ; i++) dp[i][0] = (vp[i - 1].first >= s[i] ? -1 : vp[i - 1].second); for(int j = 1 ; j < LOG ; j++) for(int i = 1 ; i <= n ; i++) dp[i][j] = (dp[i][j - 1] == -1 ? -1 : dp[dp[i][j - 1]][j - 1]); } int result(int fir , int las){ int res = 0; for(int i = LOG - 1 ; i >= 0 ; i--){ int idx = dp[las][i]; if(idx == -1) continue; //if(s[dp[dp[las][i]][i]] > s[idx]) //idx = -1; //break; if(s[idx] <= e[fir]) continue; las = idx; res |= (1 << i); } // cout << "ajab " << las << '\n'; if(dp[las][0] == -1) return -1; else return res; } void output(){ while(q--){ int fir , las; cin >> fir >> las; if(fir == las){ cout << 0 << '\n'; continue; } if(e[fir] > e[las]){ cout << "impossible" << '\n'; continue; } else if(e[fir] <= e[las] && e[fir] >= s[las]){ cout << 1 << '\n'; continue; } int ans = result(fir , las); if(ans == -1) cout << "impossible" << '\n'; else cout << ans + 2 << '\n'; } } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); clr(); cin >> n >> q; for(int i = 1 ; i <= n ; i++){ cin >> s[i] >> e[i]; vec.push_back(s[i]); vec.push_back(e[i]); } compress(); cal(); find_dp(); // for(int i = 1 ; i <= n ; i++) // cout << dp[i][0] << '\n'; output(); 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...