Submission #602967

#	Time	Username	Problem	Language	Result	Execution time	Memory
602967		MohamedAhmed04	Event Hopping (BOI22_events)	C++14	30 / 100	190 ms	18476 KiB

events

#include <bits/stdc++.h>

using namespace std ;

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 to[MAX][20] ;

int query(int a , int b)
{
	if(a == b)
		return 0 ;
	int x = R[a] , y = L[b] ;
	int ans = 0 ;
	for(int i = 19 ; i >= 0 ; --i)
	{
		if(to[x][i] < y)
			x = to[x][i] , ans += (1 << i) ;
	}
	if(x >= y && x <= R[b])
		return (ans+1) ;
	else if(to[x][0] >= y && to[x][0] <= R[b])
		return (ans+2) ;
	else
		return (-1) ;
}

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] ;
	compress() ;
	for(int i = 1 ; i <= n ; ++i)
		to[L[i]][0] = R[i] ;
	for(int i = 1 ; i <= 2*n ; ++i)
	{
		to[i][0] = max(to[i][0] , to[i-1][0]) ;
		if(to[i][0] < i)
			to[i][0] = 2*n+1 ;
	}
	to[2*n+1][0] = 2*n+1 ;
	for(int j = 1 ; j < 20 ; ++j)
	{
		for(int i = 1 ; i <= 2*n+1 ; ++i)
			to[i][j] = to[to[i][j-1]][j-1] ;
	}
	while(q--)
	{
		int x , y ;
		cin>>x>>y ;
		int ans = query(x , y) ;
		if(ans != -1)
			cout<<ans<<"\n" ;
		else
			cout<<"impossible\n" ;
	}
}

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