| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 960763 | Trisanu_Das | Event Hopping (BOI22_events) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
const int inf = 1e9 ;
const int MAX = 2e5 + 10 ;
int L[MAX], R[MAX], n, q, dp[MAX], ans[MAX];
vector<array<int , 3> > v;
vector<pair<int, int> > queries[MAX] ;
void compress() {
vector<int> v ;
for(int i = 1; i <= n; i++) v.push_back(L[i]) , v.push_back(R[i]) ;
sort(v.begin(), v.end()) ;
v.erase(unique(v.begin(), v.end()), v.end()) ;
for(int i = 1 ; i <= n ; i++) {
L[i] = lower_bound(v.begin(), v.end(), L[i]) - v.begin() ;
R[i] = lower_bound(v.begin(), v.end(), R[i]) - v.begin() ;
L[i]++ , R[i]++ ;
}
}
bool cmp(array<int , 3>&a , array<int , 3>&b) {
if(a[1] != b[1]) return (a[1] < b[1]) ;
else return (a[0] < b[0]) ;
}
void solve(int st) {
if(!queries[st].size()) return;
for(int i = 1 ; i <= n ; i++) dp[i] = inf;
dp[st] = 0;
stack<int> s;
s.push(st);
for(auto &a : v){
int l = a[0], r = a[1], idx = a[2] ;
if(idx == st || R[s.top()] > r) continue;
int last = -1 ;
while(s.size() && R[s.top()] >= l) {
last = s.top() ;
s.pop() ;
}
if(last == -1) continue;
s.push(last) , s.push(idx) ;
dp[idx] = dp[last] + 1 ;
}
for(auto &p : queries[st]) ans[p.second] = dp[p.first];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >>q ;
for(int i = 1; i <= n; i++) cin >> L[i] >> R[i] ;
for(int i = 1; i <= q; i++) {
int x, y; cin >> x >> y ;
queries[x].push_back(y, i) ;
}
compress() ;
for(int i = 1; i <= n; i++) v.push_back({L[i] , R[i] , i}) ;
sort(v.begin() , v.end() , cmp) ;
for(int i = 1; i <= n; i++) solve(i) ;
for(int i = 1; i <= q; i++) {
if(ans[i] != inf) cout << ans[i] << '\n' ;
else cout << "impossible\n" ;
}
}