제출 #603164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603164		MohamedAhmed04	Event Hopping (BOI22_events)	C++14	40 / 100	1581 ms	11016 KiB

events

#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 2e5 + 10 ;

int L[MAX] , R[MAX] ;
int n , q ;

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]++ ;
	}
}

int dp[MAX] , ans[MAX] ;

vector< array<int , 3> >v ;

vector< pair<int , int> >queries[MAX] ;

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(0) ;
	cin.tie(0) ;
	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].emplace_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" ;
	}
	return 0 ;
}

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