fork download 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define newl '\n'
  5.  
  6. using namespace std;
  7. const ll INF = 4e18;
  8.  
  9.  
  10. int n,m,q;
  11. std::vector<std::vector<char>> a;
  12. std::vector<std::vector<int>> s,lim;
  13. std::vector<int> w,h,stone,ans;
  14.  
  15. void readData(){
  16.     std::cin >> n >> m >> q;
  17.     a.assign(n + 1,std::vector<char>(m + 1,0));
  18.     s.assign(n + 1,std::vector<int>(m + 1,0));
  19.     lim.assign(n + 1,std::vector<int>(m + 1,0));
  20.     ans.assign(q + 1,0);
  21.     w.assign(q + 1,0);
  22.     h.assign(q + 1,0);
  23.     stone.assign(q + 1,0);
  24.     for(int i = 1;i <= n;++i){
  25.         for(int j = 1;j <= m;++j){
  26.             std::cin >> a[i][j];
  27.         }
  28.     }
  29.     for(int i = 1;i <= q;++i){
  30.         std::cin >> w[i] >> h[i] >> stone[i];
  31.     }
  32. }
  33. void calc(int k){
  34.     std::vector<int> prev(m + 1,0);
  35.     for(int i = 1;i <= n;++i){
  36.         for(int j = 1;j <= m;++j){
  37.             s[i][j] = s[i - 1][j];
  38.             s[i][j] += a[i][j] == '#';
  39.             while(s[i][j] - s[prev[j]][j] > k){
  40.                 ++prev[j];
  41.             }
  42.             lim[i][j] = i - prev[j];
  43. //            std::cout << lim[i][j] << " ";
  44.         }
  45. //        std::cout << newl;
  46.     }
  47. }
  48. void calc_ans(std::vector<int> query_index){
  49.     std::vector<std::vector<int>> mat(n + 3,std::vector<int>(m + 3,0));
  50.     for(int i = 1;i <= n;++i){
  51.         std::stack<int> st;
  52.         st.push(0);
  53.         for(int j = 1;j <= m;++j){
  54.             while(st.top() != 0 && lim[i][j] <= lim[i][st.top()]){
  55. //                int it = st.top();
  56.                 int v = lim[i][st.top()];
  57.                 st.pop();
  58.                 int v1 = std::max(lim[i][st.top()],lim[i][j]);
  59.                 int len = j - st.top() - 1;
  60.                 ++mat[v][len];
  61.                 --mat[v1][len];
  62. //                std::cout << "IMP " << v << " " << v1 << " " << len << newl;
  63.             }
  64.             st.push(j);
  65.         }
  66.         while(st.top() != 0){
  67. //            int it = st.top();
  68.             int v = lim[i][st.top()];
  69.             st.pop();
  70.             int v1 = lim[i][st.top()];
  71.             int len = m - st.top();
  72. //            std::cout << "IMP " << v << " " << v1 << " " << len << newl;
  73.             ++mat[v][len];
  74.             --mat[v1][len];
  75.         }
  76.     }
  77.     for(int i = n;i >= 1;--i){
  78.         for(int j = 1;j <= m;++j){
  79.             mat[i][j] += mat[i + 1][j];
  80.         }
  81.     }
  82.     for(int i = 1;i <= n;++i){
  83.         int total = 0;
  84.         for(int j = m;j >= 1;--j){
  85.             total += mat[i][j];
  86.             mat[i][j] = mat[i][j + 1] + total;
  87.         }
  88.     }
  89.     for(int cur : query_index){
  90.         ans[cur] = mat[w[cur]][h[cur]];
  91.     }
  92. }
  93. void solve(){
  94.     for(int k = 0;k <= 5;++k){
  95.         std::vector<int> query_index;
  96.         for(int i = 1;i <= q;++i){
  97.             if(stone[i] == k){
  98.                 query_index.emplace_back(i);
  99.             }
  100.         }
  101.         calc(k);
  102.         calc_ans(query_index);
  103.     }
  104.     for(int i = 1;i <= q;++i){
  105.         std::cout << ans[i] << newl;
  106.     }
  107. }
  108. int main()
  109. {
  110.     ios_base::sync_with_stdio(0);
  111.     cin.tie(0);
  112.     readData();
  113.     solve();
  114.     return 0;
  115. }
  116. /*
  117. 5 6 1
  118. 1 2 5
  119. 2 3 5
  120. 1 4 10
  121. 4 3 2
  122. 3 5 3
  123. 4 5 8
  124. 1 5
  125.  
  126. 4 3 1
  127. 1 2 3
  128. 1 3 4
  129. 1 4 5
  130. 1 3
  131.  
  132.  
  133. */
  134.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/phQcpM
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!