Submission #826308

#	Time	Username	Problem	Language	Result	Execution time	Memory
826308		MohamedAhmed04	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	513 ms	112748 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

int arr[MAX] ;
int n , q ;

vector<int>v[MAX] ;
int prv[MAX] , nxt[MAX] ;
int L[MAX] , R[MAX] ;

int last[MAX] ;

int table[MAX][20] , lg[MAX] ;

void build()
{
	lg[1] = 0 ;
	for(int i = 2 ; i <= n ; ++i)
		lg[i] = lg[i/2] + 1 ;
	for(int i = 1 ; i <= n ; ++i)
		table[i][0] = nxt[i] ;
	for(int j = 1 ; (1 << j) <= n ; ++j)
	{
		for(int i = 1 ; i + (1 << j) - 1 <= n ; ++i)
			table[i][j] = max(table[i][j-1] , table[i + (1 << (j-1))][j-1]) ;
	}
}

int RmaxQ(int l , int r)
{
	int k = lg[r-l+1] ;
	return max(table[l][k] , table[r - (1 << k) + 1][k]) ;
}

void preprocess()
{
	for(int i = 1 ; i <= n ; ++i)
	{
		prv[i] = last[arr[i-1]] ;
		for(auto &x : v[i])
			last[x] = i ;
	}
	for(int i = 0 ; i <= n ; ++i)
		last[i] = n+1 ;
	for(int i = n ; i >= 1 ; --i)
	{
		nxt[i] = last[arr[i]] ;
		for(auto &x : v[i])
			last[x] = i ;
	}
	build() ;
}

vector<int>Erase[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n-1 ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= n ; ++i)
	{
		int sz ;
		cin>>sz ;
		v[i].resize(sz) ;
		for(auto &x : v[i])
			cin>>x ;
	}
	preprocess() ;
	set<int>s ;
	s.insert(n) ;
	for(int i = n ; i >= 1 ; --i)
	{
		for(auto &x : Erase[i])
			s.erase(x) ;
		R[i] = *s.begin() ;
		if(prv[i] == 0)
		{
			s.insert(i-1) ;
			continue ;
		}
		int l = prv[i] , r = i-2 ;
		int idx = -1 ;
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			if(RmaxQ(prv[i] , mid) >= i)
				idx = mid , r = mid-1 ;
			else
				l = mid+1 ;
		}
		if(idx != -1)
			s.insert(i-1) , Erase[idx].push_back(i-1) ; 
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		L[i] = i ;
		int l = 1 , r = i-1 ;
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			if(RmaxQ(mid , i-1) <= R[i])
				L[i] = mid , r = mid-1 ;
			else
				l = mid+1 ;
		}
	}
	cin>>q ;
	while(q--)
	{
		int x , y ;
		cin>>x>>y ;
		if(y >= L[x] && y <= R[x])
			cout<<"YES\n" ;
		else
			cout<<"NO\n" ;
	}
	return 0 ;
}		

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75