oj.uz

Submission #163724

# Submission time Handle Problem Language Result Execution time Memory
163724 2019-11-14T19:45:30 Z MohamedAhmed04 Strah (COCI18_strah) C++14
110 / 110
 428 ms 67492 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 504 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 4984 KB Output is correct
2 Correct 15 ms 4988 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 4948 KB Output is correct

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 25768 KB Output is correct
2 Correct 252 ms 51496 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 45432 KB Output is correct
2 Correct 378 ms 65216 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 28964 KB Output is correct
2 Correct 273 ms 54264 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 22648 KB Output is correct
2 Correct 296 ms 63252 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 67492 KB Output is correct
2 Correct 428 ms 67328 KB Output is correct