oj.uz

Submission #163717

# Submission time Handle Problem Language Result Execution time Memory
163717 2019-11-14T19:01:55 Z MohamedAhmed04 Strah (COCI18_strah) C++14
110 / 110
 863 ms 71112 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] , l[MAX] , r[MAX] , len[MAX][MAX] , last[MAX] ;
int n , m ;
long long ans = 0ll ;

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

void build(int node , int l , int r , int i)
{
	if(l == r)
	{
		tree[node] = {arr2[i][l] , l} ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid , i) ;
	build(node << 1 | 1 , mid + 1 , r , i) ;
	tree[node] = min(tree[node << 1] , tree[node << 1 | 1]) ;
}

pair<int , int> query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return {inf , -1} ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	pair<int , int>a = query(node << 1 , l , mid , from , to) ;
	pair<int , int>b = query(node << 1 | 1 , mid + 1 , r , from , to) ;
	return min(a , b) ;
}

long long divide_and_conquer(int l , int r , int prv , int i)
{
	if(l > r)
		return 0 ;
	pair<int , int>p = query(1 , 1 , m , 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)
{
	build(1 , 1 , m , 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 376 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 376 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 20 ms 4856 KB Output is correct
2 Correct 20 ms 4984 KB Output is correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 26104 KB Output is correct
2 Correct 516 ms 53256 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 47192 KB Output is correct
2 Correct 833 ms 68564 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 30384 KB Output is correct
2 Correct 561 ms 56624 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 22884 KB Output is correct
2 Correct 617 ms 66000 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 71008 KB Output is correct
2 Correct 812 ms 71112 KB Output is correct