oj.uz

답안 #602967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602967 2022-07-23T13:32:54 Z MohamedAhmed04 Event Hopping (BOI22_events) C++14
30 / 100
 190 ms 18476 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(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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 119 ms 17356 KB Output is correct
3 Correct 125 ms 17432 KB Output is correct
4 Correct 118 ms 17624 KB Output is correct
5 Correct 123 ms 18012 KB Output is correct
6 Correct 139 ms 18008 KB Output is correct
7 Correct 129 ms 18076 KB Output is correct
8 Correct 119 ms 18472 KB Output is correct
9 Correct 128 ms 18464 KB Output is correct
10 Correct 156 ms 18360 KB Output is correct
11 Correct 148 ms 18360 KB Output is correct
12 Correct 107 ms 18452 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 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 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 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 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 17360 KB Output is correct
2 Correct 126 ms 17536 KB Output is correct
3 Correct 142 ms 17356 KB Output is correct
4 Correct 135 ms 18476 KB Output is correct
5 Correct 180 ms 18268 KB Output is correct
6 Correct 190 ms 18036 KB Output is correct
7 Correct 166 ms 18044 KB Output is correct
8 Correct 151 ms 18272 KB Output is correct
9 Correct 109 ms 17336 KB Output is correct
10 Correct 150 ms 17736 KB Output is correct
11 Correct 139 ms 17556 KB Output is correct
12 Correct 140 ms 17688 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 119 ms 17356 KB Output is correct
3 Correct 125 ms 17432 KB Output is correct
4 Correct 118 ms 17624 KB Output is correct
5 Correct 123 ms 18012 KB Output is correct
6 Correct 139 ms 18008 KB Output is correct
7 Correct 129 ms 18076 KB Output is correct
8 Correct 119 ms 18472 KB Output is correct
9 Correct 128 ms 18464 KB Output is correct
10 Correct 156 ms 18360 KB Output is correct
11 Correct 148 ms 18360 KB Output is correct
12 Correct 107 ms 18452 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Incorrect 1 ms 468 KB Output isn't correct
19 Halted 0 ms 0 KB -