oj.uz

Submission #602958

# Submission time Handle Problem Language Result Execution time Memory
602958 2022-07-23T13:25:31 Z MohamedAhmed04 Event Hopping (BOI22_events) C++14
0 / 100
 132 ms 18040 KB 
#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(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 117 ms 17972 KB Output is correct
3 Correct 121 ms 18040 KB Output is correct
4 Incorrect 122 ms 17920 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17964 KB Output is correct
2 Correct 115 ms 17952 KB Output is correct
3 Incorrect 132 ms 17992 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 117 ms 17972 KB Output is correct
3 Correct 121 ms 18040 KB Output is correct
4 Incorrect 122 ms 17920 KB Output isn't correct
5 Halted 0 ms 0 KB -