Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int h[1005][1005];
  5.  
  6. int ans[1005][1005];
  7.  
  8. int main(){
  9. ios_base::sync_with_stdio(0);
  10. cin.tie(0);
  11. cout.tie(0);
  12.  
  13. int n, m;
  14. char c;
  15. cin>>n>>m;
  16. for(int i = 1; i <= n; i++){
  17. vector<pair<int, int> > v;
  18. v.push_back({0, 0});
  19. for(int j = 1; j <= m; j++){
  20. h[i][j] = h[i - 1][j] + 1;
  21. cin>>c;
  22. if(c == '*') h[i][j] = 0;
  23. while(!v.empty() && v.back().second >= h[i][j]) v.pop_back();
  24.  
  25. v.push_back({j, h[i][j]});
  26.  
  27. for(int l = v.size() - 2; l >= 0; l--){
  28. ans[v[l + 1].second][j - v[l].first]++;
  29. ans[v[l].second][j - v[l].first]--;
  30. }
  31. }
  32. }
  33. for(int i = n; i > 0; i--){
  34. for(int j = m; j > 0; j--){
  35. ans[i][j] += ans[i + 1][j] + ans[i][j + 1] - ans[i + 1][j + 1];
  36. }
  37. }
  38. for(int i = 1; i <= n; i++){
  39. for(int j = 1; j <= m; j++){
  40. cout<<ans[i][j]<<' ';
  41. }
  42. cout<<'\n';
  43. }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement