Advertisement
Tranvick

Untitled

Apr 16th, 2012
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #define N 1111
  4. using namespace std;
  5.  
  6. int up[N][N],left[N][N],down[N][N],right[N][N],l[N],r[N],n,m,ptr,mink,ans,kol;
  7. char c[N][N];
  8. int s[N];
  9.  
  10. pair<int,int> times[N];
  11.  
  12. inline int prev(int x){
  13.     return x&(x-1);
  14. }
  15.  
  16. inline int next(int x){
  17.     return (x<<1)-(x&(x-1));
  18. }
  19.  
  20. inline void modify(int pos,int value){
  21.     for (;pos<N;pos=next(pos)) s[pos]+=value;
  22. }
  23.  
  24. inline int get_sum(int l,int r){
  25.     if (l>r) return 0;
  26.     int k=0,p;
  27.     for (p=r;p>0;p=prev(p)) k+=s[p];
  28.     for (p=l-1;p>0;p=prev(p)) k-=s[p];
  29.     return k;
  30. }
  31.  
  32. inline void input(){
  33.     freopen("input.txt","r",stdin);
  34.     freopen("output.txt","w",stdout);
  35.     scanf("%d%d%d\n",&n,&m,&mink);
  36.     mink=mink%4?mink/4+2:mink/4+1;
  37.     for (int i=1;i<=n;i++){
  38.         for (int j=1;j<=m;j++) scanf("%c",&c[i][j]);
  39.         scanf("\n");
  40.     }
  41. }
  42.  
  43. inline void init(){
  44.     for (int i=1;i<=n;i++)
  45.         for (int j=1;j<=m;j++){
  46.             up[i][j]=c[i][j]=='#'?0:up[i-1][j]+1;
  47.             left[i][j]=c[i][j]=='#'?0:left[i][j-1]+1;
  48.         }
  49.     for (int i=n;i>=1;i--)
  50.         for (int j=m;j>=1;j--){
  51.             down[i][j]=c[i][j]=='#'?0:down[i+1][j]+1;
  52.             right[i][j]=c[i][j]=='#'?0:right[i][j+1]+1;
  53.         }
  54. }
  55.  
  56. inline void upd_ans(){
  57.     memset(s,0,sizeof(s));
  58.     kol=0;
  59.     for (int i=1;i<=ptr;i++){
  60.         if (l[i]>=mink){
  61.             modify(i,1);
  62.             times[++kol]=make_pair(l[i]+i-1,i);
  63.         }
  64.     }
  65.     sort(times+1,times+kol+1);
  66.     int f=1;
  67.     for (int i=1;i<=ptr;i++){
  68.         ans+=get_sum(i-r[i]+1,i-mink+1);
  69.         while (times[f].first==i && f<=kol){
  70.             modify(times[f].second,-1);
  71.             ++f;
  72.         }  
  73.     }
  74. }
  75.  
  76. int main(){
  77.     input();
  78.     init();
  79.     for (int I=1;I<=n;I++){
  80.         ptr=0;
  81.         for (int i=I,j=1;i<=n && j<=m;i++,j++){
  82.             l[++ptr]=min(right[i][j],down[i][j]);
  83.             r[ptr]=min(left[i][j],up[i][j]);
  84.         }        
  85.         upd_ans();
  86.     }
  87.     for (int I=2;I<=m;I++){
  88.         ptr=0;
  89.         for (int i=1,j=I;i<=n && j<=m;i++,j++){
  90.             l[++ptr]=min(right[i][j],down[i][j]);
  91.             r[ptr]=min(left[i][j],up[i][j]);
  92.         }
  93.         upd_ans();
  94.     }
  95.     printf("%d",ans);
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement