Submission #960764

#	Time	Username	Problem	Language	Result	Execution time	Memory
960764		Trisanu_Das	Event Hopping (BOI22_events)	C++17	40 / 100	1528 ms	15016 KiB

events

#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" ;
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30