Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int h[1005][1005];
- int ans[1005][1005];
- int main(){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n, m;
- char c;
- cin>>n>>m;
- for(int i = 1; i <= n; i++){
- vector<pair<int, int> > v;
- v.push_back({0, 0});
- for(int j = 1; j <= m; j++){
- h[i][j] = h[i - 1][j] + 1;
- cin>>c;
- if(c == '*') h[i][j] = 0;
- while(!v.empty() && v.back().second >= h[i][j]) v.pop_back();
- v.push_back({j, h[i][j]});
- for(int l = v.size() - 2; l >= 0; l--){
- ans[v[l + 1].second][j - v[l].first]++;
- ans[v[l].second][j - v[l].first]--;
- }
- }
- }
- for(int i = n; i > 0; i--){
- for(int j = m; j > 0; j--){
- ans[i][j] += ans[i + 1][j] + ans[i][j + 1] - ans[i + 1][j + 1];
- }
- }
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= m; j++){
- cout<<ans[i][j]<<' ';
- }
- cout<<'\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement