Submission #815422

#	Time	Username	Problem	Language	Result	Execution time	Memory
815422		MohamedAhmed04	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1148 ms	65636 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n , k , m , q ;

pair<int , int>tree[20][4 * MAX] ;

pair<int , int>Merge(pair<int , int>&a , pair<int , int>&b)
{
	return {min(a.first , b.first) , max(a.second , b.second)} ;
}

void update(int t , int node , int l , int r , int idx , pair<int , int>val)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		tree[t][node] = val ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(t , node << 1 , l , mid , idx , val) ;
	update(t , node << 1 | 1 , mid+1 , r , idx , val) ;
	tree[t][node] = Merge(tree[t][node << 1] , tree[t][node << 1 | 1]) ;
}

pair<int , int>query(int t , int node , int l , int r , int from , int to)
{
	if(from > r || to < l || from > to)
		return {1e9 , -1e9} ;
	if(l >= from && r <= to)
		return tree[t][node] ;
	int mid = (l + r) >> 1 ;
	pair<int , int>a = query(t , node << 1 , l , mid , from , to) ;
	pair<int , int>b = query(t , node << 1 | 1 , mid+1 , r , from , to) ;
	return Merge(a , b) ;
}

pair<int , int>to[MAX][20] ;
pair<int , int>old_to[MAX] ;

void preprocess()
{
	multiset<int>sl , sr ;
	for(int i = 1 ; i <= k-1 ; ++i)
		sl.insert(to[i][0].first) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		old_to[i] = to[i][0] ;
		sr.insert(to[i][0].second) ; 
		if(i+k-1 <= n)
			sl.insert(to[i+k-1][0].first) ;
		if(i-k >= 1)
			sr.erase(sr.find(old_to[i-k].second)) ;
		if(i > 1)
			sl.erase(sl.find(old_to[i-1].first)) ;
		to[i][0] = {*sl.begin() , *sr.rbegin()} ;
		to[i][0].first = min(to[i][0].first , i) ;
		to[i][0].second = max(to[i][0].second , i) ; 
	}
	for(int i = 1 ; i <= n ; ++i)
		update(0 , 1 , 1 , n , i , to[i][0]) ;
	for(int j = 1 ; j < 20 ; ++j)
	{
		for(int i = 1 ; i <= n ; ++i)
		{
			to[i][j] = query(j-1 , 1 , 1 , n , to[i][j-1].first , to[i][j-1].second) ;
			update(j , 1 , 1 , n , i , to[i][j]) ;
		}
	}
}

int solve(int x , int y)
{
	if(y < to[x][19].first || y > to[x][19].second)
		return -1 ;
	int l = x , r = x , ans = 1 ;
	for(int i = 19 ; i >= 0 ; --i)
	{
		pair<int , int>p = query(i , 1 , 1 , n , l , r) ;
		if(y < p.first || y > p.second)
		{
			ans += (1 << i) ;
			l = p.first , r = p.second ;
		}
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	cin>>m ;
	for(int i = 1 ; i <= n ; ++i)
		to[i][0] = {1e9 , -1e9} ;
	for(int i = 0 ; i < m ; ++i)
	{
		int l , r ;
		cin>>l>>r ;
		if(l > r)
			to[l][0].first = min(to[l][0].first , r) ;
		else
			to[l][0].second = max(to[l][0].second , r) ;
	}
	preprocess() ;
	cin>>q ;
	while(q--)
	{
		int x , y ;
		cin>>x>>y ;
		cout<<solve(x , y)<<"\n" ;
	}
	return 0 ;
}		

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13