oj.uz

Submission #163806

# Submission time Handle Problem Language Result Execution time Memory
163806 2019-11-15T12:54:20 Z MohamedAhmed04 Strah (COCI18_strah) C++17
110 / 110
 437 ms 67288 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4860 KB Output is correct
2 Correct 13 ms 4856 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4856 KB Output is correct
2 Correct 13 ms 4860 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4856 KB Output is correct
2 Correct 13 ms 4840 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 25156 KB Output is correct
2 Correct 336 ms 51068 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 44936 KB Output is correct
2 Correct 390 ms 65144 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 29032 KB Output is correct
2 Correct 296 ms 54264 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22740 KB Output is correct
2 Correct 290 ms 63284 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 67228 KB Output is correct
2 Correct 437 ms 67288 KB Output is correct