Submission #163724

#	Time	Username	Problem	Language	Result	Execution time	Memory
163724		MohamedAhmed04	Strah (COCI18_strah)	C++14	110 / 110	428 ms	67492 KiB

strah

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2005 ;
const int inf = 1e9 ;

char arr[MAX][MAX] ;
long long arr2[MAX][MAX] , calc[MAX][MAX] , lg[MAX];
pair<int , int>Min[12][MAX] ;
int n , m ;
long long ans = 0ll ;

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

void preprocess(int i)
{
	lg[1] = 0 ;
	for(int j = 2 ; j <= m ; ++j)
		lg[j] = lg[j/2] + 1 ;
	for(int ii = 0 ; ii < 12 ; ++ii)
	{
		for(int j = 0 ; j <= m ; ++j)
			Min[ii][j] = {inf , j} ;
	}
	for(int j = 1 ; j <= m ; ++j)
		Min[0][j] = {arr2[i][j] , j} ;
	for(int j = 1 ; (1 << j) <= m ; ++j)
	{
		for(int ii = 1 ; (ii + (1 << j) - 1) <= m ; ++ii)
			Min[j][ii] = min(Min[j-1][ii] , Min[j-1][ii + (1 << (j-1))]) ;
	}
}

pair<int , int>RminQ(int l , int r)
{
	int j = lg[r-l+1] ;
	return min(Min[j][l] , Min[j][r - (1 << j) + 1]) ;
}

long long divide_and_conquer(int l , int r , int prv , int i)
{
	if(l > r)
		return 0 ;
	pair<int , int>p = RminQ(l , r) ;
 	long long a = calc[p.first][r-l+1] - calc[prv][r-l+1] ;
	return (a + divide_and_conquer(l , p.second-1 , p.first , i) + divide_and_conquer(p.second+1 , r , p.first , i)) ;
}
long long solve(int i)
{
	preprocess(i) ;
	return divide_and_conquer(1 , m , 0 , i) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
			cin>>arr[i][j] ;
	}
	calc[1][0] = 0 ;
	for(long long j = 1 ; j <= m ; ++j)
		calc[1][j] = calc[1][j-1] + (j * (j+1ll) / 2ll) ;
	for(long long i = 2 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
			calc[i][j] = calc[i-1][j] + calc[1][j] * i ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			if(arr[i][j] == '.')
				arr2[i][j] = arr2[i-1][j] + 1 ;
		}
		ans += solve(i) ;
	}
	return cout<<ans<<"\n" , 0 ;
}		

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11