oj.uz

Submission #826291

# Submission time Handle Problem Language Result Execution time Memory
826291 2023-08-15T12:22:05 Z MohamedAhmed04 Long Mansion (JOI17_long_mansion) C++14
0 / 100
 165 ms 47912 KB 
#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(l , 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 16 ms 24356 KB Output is correct
3 Correct 17 ms 24608 KB Output is correct
4 Incorrect 13 ms 24196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 16 ms 24356 KB Output is correct
3 Correct 17 ms 24608 KB Output is correct
4 Incorrect 13 ms 24196 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 47912 KB Output is correct
2 Correct 141 ms 47620 KB Output is correct
3 Incorrect 165 ms 47264 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 16 ms 24356 KB Output is correct
3 Correct 17 ms 24608 KB Output is correct
4 Incorrect 13 ms 24196 KB Output isn't correct
5 Halted 0 ms 0 KB -