Submission #827650

#	Time	Username	Problem	Language	Result	Execution time	Memory
827650		MohamedAhmed04	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	592 ms	17416 KiB

abduction2

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e4 + 10 ;

int a[MAX] , b[MAX] ;
int n , m , q ;

int table_row[MAX][20] , table_col[MAX][20] ;
int lg[MAX] ;

void preprocess()
{
	int sz = max(n , m) ;
	lg[1] = 0 ;
	for(int i = 2 ; i <= sz ; ++i)
		lg[i] = lg[i/2] + 1 ;
	for(int i = 1 ; i <= sz ; ++i)
		table_row[i][0] = a[i] , table_col[i][0] = b[i] ;
	for(int j = 1 ; (1 << j) <= sz ; ++j)
	{
		for(int i = 1 ; i + (1 << j) - 1 <= sz ; ++i)
		{
			table_row[i][j] = max(table_row[i][j-1] , table_row[i + (1 << (j-1))][j-1]) ;
			table_col[i][j] = max(table_col[i][j-1] , table_col[i + (1 << (j-1))][j-1]) ;
		}
	}
}

int Range_Row_Max(int l , int r)
{
	if(l > r)
		return 0 ;
	int k = lg[r-l+1] ;
	return max(table_row[l][k] , table_row[r - (1 << k) + 1][k]) ;
}

int Range_Col_Max(int l , int r)
{
	if(l > r)
		return 0 ;
	int k = lg[r-l+1] ;
	return max(table_col[l][k] , table_col[r - (1 << k) + 1][k]) ;
}

int FindLeft(int i , int j)
{
	if(i < 1 || i > n || j < 1 || j > m)
		return -1 ;
	int l = 1 , r = j-1 ;
	int idx = -1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(Range_Col_Max(mid , j-1) > a[i])
			idx = mid , l = mid+1 ;
		else
			r = mid-1 ;
	}
	return idx ;
}

int FindRight(int i , int j)
{
	if(i < 1 || i > n || j < 1 || j > m)
		return -1 ;
	int l = j+1 , r = m ;
	int idx = -1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(Range_Col_Max(j+1 , mid) > a[i])
			idx = mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return idx ;
}

int FindUp(int i , int j)
{
	if(i < 1 || i > n || j < 1 || j > m)
		return -1 ;
	int l = 1 , r = i-1 ;
	int idx = -1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(Range_Row_Max(mid , i-1) > b[j])
			idx = mid , l = mid+1 ;
		else
			r = mid-1 ;
	}
	return idx ;
}

int FindDown(int i , int j)
{
	if(i < 1 || i > n || j < 1 || j > m)
		return -1 ;
	int l = i+1 , r = n ;
	int idx = -1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(Range_Row_Max(i+1 , mid) > b[j])
			idx = mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return idx ;
}

vector< pair<int , int> >vp ;
vector< pair<int , long long> >vr[MAX] , vc[MAX] ;

long long solve(int i , int j)
{
	for(int i = 1 ; i <= max(n , m) ; ++i)
		vr[i].clear() , vc[i].clear() ;
	long long ans = 0 ;
	//preprocess some points
	int j2 = FindLeft(i , j) ;
	if(j2 == -1)
		ans = max(ans , 1ll*j-1) ;
	else
		vc[j2].emplace_back(i , j-j2) ;
	j2 = FindRight(i , j) ;
	if(j2 == -1)
		ans = max(ans , 1ll*m-j) ;
	else
		vc[j2].emplace_back(i , j2-j) ;
	int i2 = FindUp(i , j) ;
	if(i2 == -1)
		ans = max(ans , 1ll*i-1) ;
	else
		vr[i2].emplace_back(j , i-i2) ;
	i2 = FindDown(i , j) ;
	if(i2 == -1)
		ans = max(ans , 1ll*n-i) ;
	else
		vr[i2].emplace_back(j , i2-i) ;
	//Answer
	for(auto &p : vp)
	{
		if(p.second > 0)
		{
			i2 = p.second ;
			sort(vr[i2].begin() , vr[i2].end()) ;
			//Add to right columns
			long long prv = 2e9 , Max = -1e9 ;
			for(auto &p2 : vr[i2])
			{
				if(Range_Col_Max(prv+1 , p2.first-1) > a[i2])
				{
					j2 = FindRight(i2 , prv) ;
					vc[j2].emplace_back(i2 , Max + j2 - prv) ;
					Max = p2.second ;
				}
				else
					Max = max(p2.second , Max + p2.first-prv) ;
				prv = p2.first ;
			}
			j2 = FindRight(i2 , prv) ;
			if(j2 == -1)
				ans = max(ans , Max + m - prv) ;
			else
				vc[j2].emplace_back(i2 , Max + j2 - prv) ;
			//Add to left columns
			reverse(vr[i2].begin() , vr[i2].end()) ;
			prv = -2e9 , Max = -1e9 ;
			for(auto &p2 : vr[i2])
			{
				if(Range_Col_Max(p2.first+1 , prv-1) > a[i2])
				{
					j2 = FindLeft(i2 , prv) ;
					vc[j2].emplace_back(i2 , Max + prv - j2) ;
					Max = p2.second ;
				}
				else
					Max = max(p2.second , Max + prv - p2.first) ;
				prv = p2.first ;
			}
			j2 = FindLeft(i2 , prv) ;
			if(j2 == -1)
				ans = max(ans , Max + prv - 1) ;
			else
				vc[j2].emplace_back(i2 , Max + prv - j2) ;
		}
		else
		{
			j2 = -1 * p.second ;
			sort(vc[j2].begin() , vc[j2].end()) ;
			//Add to down rows
			long long prv = 2e9 , Max = -1e9 ;
			for(auto &p2 : vc[j2])
			{
				if(Range_Row_Max(prv+1 , p2.first-1) > b[j2])
				{
					i2 = FindDown(prv , j2) ;
					vr[i2].emplace_back(j2 , Max + i2 - prv) ;
					Max = p2.second ;
				}
				else
					Max = max(p2.second , Max + p2.first-prv) ;
				prv = p2.first ;
			}
			i2 = FindDown(prv , j2) ;
			if(i2 == -1)
				ans = max(ans , Max + n - prv) ;
			else
				vr[i2].emplace_back(j2 , Max + i2 - prv) ;
			//Add to up columns
			reverse(vc[j2].begin() , vc[j2].end()) ;
			prv = -2e9 , Max = -1e9 ;
			for(auto &p2 : vc[j2])
			{
				if(Range_Row_Max(p2.first+1 , prv-1) > b[j2])
				{
					i2 = FindUp(prv , j2) ;
					vr[i2].emplace_back(j2 , Max + prv - i2) ;
					Max = p2.second ;
				}
				else
					Max = max(p2.second , Max + prv - p2.first) ;
				prv = p2.first ;
			}
			i2 = FindUp(prv , j2) ;
			if(i2 == -1)
				ans = max(ans , Max + prv - 1) ;
			else
				vr[i2].emplace_back(j2 , Max + prv - i2) ;
		}
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>q ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>a[i] ;
	for(int i = 1 ; i <= m ; ++i)
		cin>>b[i] ;
	for(int i = 1 ; i <= n ; ++i)
		vp.emplace_back(a[i] , i) ;
	for(int i = 1 ; i <= m ; ++i)
		vp.emplace_back(b[i] , -i) ;
	sort(vp.begin() , vp.end()) ;
	preprocess() ;
	while(q--)
	{
		int i , j ;
		cin>>i>>j ;
		cout<<solve(i , j)<<"\n" ;
	}
	return 0 ;
}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56