#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
#include<string.h>
using namespace std;
#define pb push_back
#define mp make_pair
/// UMJESTO FORMULE PROBATI DP-OM IZRACUNATI!
/// DP : DP[X][1] = X*(X+1)/2, PRELAZ : DP[X][Y] = DP[X][Y-1] + X*(X+1)*Y*(Y+1)/4 , RJESENJE NADJEMO: DP VELKI - DP MALI 1 - DP MALI 2. DVA MALA PODJELI KVADRAT U SREDINI
int maxn=1000000000;
int n,m;
char a[2010][2010];
long long visina[2010];
long long h[2010][2010];
int desno[2010][2010],levo[2010][2010];
long long tree[400010];
long long treemax[400010];
long long dp[2010][2010];
long long res=0;
vector<int>tmp;
void upd( int idx, int l, int r, int pos, int val, bool type )
{
if( l > pos || r < pos || l>r ) return;
if( l==r ){
if(type==0)
tree[idx]=val;
else treemax[idx]=val;
return;
}
int mid=(l+r)/2;
//cout << (idx << 1) +1 << " " << idx << " samo da znas" <<endl;
upd( (idx<<1), l ,mid, pos,val,type );
upd( ( idx<<1 ) + 1, mid+1,r,pos,val,type );
if( type==0 )
tree[idx]=min( tree[ (idx<<1) ], tree[ (idx<<1) + 1 ] );
else treemax[idx]=max( treemax[ (idx<<1) ], treemax[ ( idx << 1 ) + 1 ] );
}
int rmq( int idx, int l, int r, int i, int j, bool type )
{
if( l > j || r < i || l> r ){
if( type==1 ) return -1;
else return maxn;
}
if( l >= i && r <= j ){
if( type ) return treemax[idx];
else return tree[idx];
}
int mid=(l+r)/2;
int val1=rmq( (idx<<1),l,mid,i,j,type );
int val2=rmq( ( idx<<1 )+1,mid+1,r,i,j,type );
if( type==0 ) return min( val1,val2 );
else return max( val1,val2 );
}
void check( int i,int j, bool w )
{
long long val=a[i][j];
if( val == '#' ){ /// ocistimo fenvikovo
/* for( int k=0;k<tmp.size();k++ ){
upd( 1,0,n-1,tmp[k], maxn );
}*/
// visina[j] = (long long)(n-i-1); /// nova pregrada znaci novo ogranicenje za visinu
if( w==0 )
visina[j]=i;
upd( 1,0,n,0, j,1-w ); /// 1-w, jer ako je w= 0 trazimo max, a max je 1 i obratno
tmp.pb( 0 );
}
else{ /// inace, dodamo na rezultat pa dodamo u fenwikovo
if( w==0 )
h[i][j] = i-visina[j];
// h[i][j]= i-visina[j]; /// treba jos skontat kako update visinu
// if( i==0 && j == 2 ) cout << visina[j] << " wtf " << h[i][j]<<endl;
/// upd( 1,0,n-1, h[i][j], j ); /// upd prije ili poslije?!
if(w) {
// }
desno[i][j] = rmq( 1,0,n,0, h[i][j]-1,0 ); /// desno udara strogo u manje, a lijevo udara i u isti.. NE NADJE DOBRO DESNI, NE ZNAM STO
desno[i][j] = min( desno[i][j], m );
// tmp.pb( h[i][j] );
}
else{
// if( i == 0 && j == 2 ) cout << rmq( 1,0,n,0,0,1 ) << " eee e" <<endl;
levo[i][j] = rmq( 1,0,n, 0, h[i][j] ,1 ); /// 1 je za max, 0 je za min
if( levo[i][j] == maxn ) levo[i][j]=-1;
// tmp.pb( h[i][j] );
}
// if( w && i==0 && j==2 ) cout << h[i][j] << " begee " <<endl;
upd( 1,0,n, h[i][j], j,1-w );
tmp.pb( h[i][j] );
}
}
int main()
{
cin>>n>>m;
for( long long i=1;i<=n;i++ ) dp[i][1] = (i*(i+1))/2;
for( long long i=1;i<=n;i++ ){
for( long long j=2;j<=m;j++ ) dp[i][j] = dp[i][j-1] + ( i*(i+1)*j*(j+1) )/4;
}
// cout << dp[n][m] <<endl;
// cout << dp[3][2] << " " << dp[3][3] << " bezi ba" <<endl;
// cout << dp[1][1] << " oko " <<endl;
for( int i=0;i<= 4*(n+1);i++ ) tree[i] = maxn;
for( int i=0;i<=4*(n+1);i++ ) treemax[i]=-1;
for( int i=0;i<m;i++ ) visina[i]=-1;
for( int i=0;i<n;i++ ){
for( int j=0;j<m;j++ ){
cin>>a[i][j];
check( i,j,0 );
}
/// kad god predjemo u novi red, takodjer treba obrisati fenvikovo
for( int k=0;k<tmp.size();k++ ) {
upd( 1,0,n,tmp[k],-1,1 );
}
tmp.clear();
}
// cout << rmq( 1,0,n-1,0,n ) << " bolaaaaa " <<endl;
// for( int i=0;i<m;i++ ) visina[i]=-1; /// resetujemo visine
for( int i=0;i<n;i++ ){
for( int j=m-1;j>=0;j-- ){
check( i,j,1 );
}
/// kad god predjemo u novi red, takodjer treba obrisati fenvikovo
for( int k=0;k<tmp.size();k++ ) upd( 1,0,n,tmp[k],maxn,0 );
tmp.clear();
// for( int i=0;i<=4*n;i++ ) tree[i]=maxn;
}
// cout << rmq( 1,0,n-1,0,n ) << " bolaaaaa " <<endl;
for( int i=0;i<n;i++ ){
for( int j=0;j<m;j++ ){
// h[i][j] -= (n-i-1) ;
if( a[i][j] == '#' ) continue;
long long a= (long long)(desno[i][j] - levo[i][j] - 1);
long long b= ( long long ) h[i][j];
long long mali1 = desno[i][j] - j-1;
long long mali2 = j - levo[i][j]-1;
/// ovdje sad ide formula za onaj pravougaonik koju moram izracunat jos na papiru
res+= dp[b][a];
res-= dp[ b ][mali1];
res-=dp[b][mali2];
}
}
cout<<res<<endl;
///moram dodat njih same, to sam zaboravio
}
/*
5
1
2
1
2
2
*/
Compilation message
strah.cpp: In function 'int main()':
strah.cpp:125:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int k=0;k<tmp.size();k++ ) {
~^~~~~~~~~~~
strah.cpp:137:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int k=0;k<tmp.size();k++ ) upd( 1,0,n,tmp[k],maxn,0 );
~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
50 ms |
8028 KB |
Output is correct |
| 2 |
Correct |
55 ms |
8000 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
50 ms |
7956 KB |
Output is correct |
| 2 |
Correct |
53 ms |
7932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
47 ms |
7928 KB |
Output is correct |
| 2 |
Correct |
54 ms |
8028 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
579 ms |
39532 KB |
Output is correct |
| 2 |
Execution timed out |
1066 ms |
68836 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1063 ms |
62104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1047 ms |
43940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
187 ms |
39672 KB |
Output is correct |
| 2 |
Execution timed out |
1078 ms |
63332 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1073 ms |
69788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
