fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <cstdlib>
  9. #include <cstdio>
  10. #include <utility>
  11. #include <iomanip>
  12. #include <assert.h>
  13. #include <complex>
  14. #define MP make_pair
  15. #define PB push_back
  16. #define int long long
  17. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  18. #define RE(i, n) FOR(i, 1, n)
  19. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  20. #define REP(i, n) for(int i = 0;i <(n); ++i)
  21. #define VAR(v, i) __typeof(i) v=(i)
  22. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  23. #define ALL(x) (x).begin(), (x).end()
  24. #define SZ(x) ((int)(x).size())
  25. #ifdef LOCAL
  26. #define debug(x) {cerr <<#x <<" = " <<x <<"\n"; }
  27. #define debug2(x, y) {cerr <<#x <<" = " <<x <<", "<<#y <<" = " <<y <<"\n";}
  28. #define debug3(x, y, z) {cerr <<#x <<" = " <<x <<", "<<#y <<" = " <<y <<", "<<#z<<" = "<<z<<"\n";}
  29. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  30. using std::cerr;
  31. #else
  32. #define debug(x)
  33. #define debug2(x, y)
  34. #define debug3(x, y, z)
  35. #define debugv(x)
  36. #define cerr if(0)cout
  37. #endif
  38. #define make(type, x) type x; cin>>x;
  39. #define make2(type, x, y) type x, y; cin>>x>>y;
  40. #define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
  41. #define make4(type, x, y, z, t) type x, y, z, t; cin>>x>>y>>z>>t;
  42. using std::endl;
  43. using std::cout;
  44. using std::cin;
  45. using std::vector;
  46. using std::set;
  47. using std::map;
  48. using std::pair;
  49. using std::max;
  50. using std::min;
  51. using std::ostream;
  52. using std::fixed;
  53. using std::ios_base;
  54. using std::setprecision;
  55. using std::make_pair;
  56. using std::string;
  57. using std::multiset;
  58. using std::next_permutation;
  59. using std::prev_permutation;
  60. using std::random_shuffle;
  61. using std::greater;
  62. using std::lower_bound;
  63. using std::upper_bound;
  64. using std::reverse;
  65. using std::swap;
  66. using std::complex;
  67. using std::sort;
  68. typedef long long ll;
  69. typedef long double LD;
  70. //typedef pair<int, int> PII;
  71. typedef pair<ll, ll> PII;
  72. typedef pair<ll, ll> PLL;
  73. typedef vector<ll> VI;
  74. typedef vector<int> VI;
  75. typedef vector<ll> VLL;
  76. typedef vector<pair<int, int> > VPII;
  77. typedef vector<pair<ll, ll> > VPLL;
  78.  
  79. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  80. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  81. template<class T1, class T2>
  82. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  83.  
  84. const int N = 2e3;
  85. int rec[N][N];
  86. int b[N][N];
  87. int dep[N][N];
  88. #undef int
  89. int main() {
  90. #define int long long
  91.  
  92.   //ios_base::sync_with_stdio(0);
  93.   cout << fixed << setprecision(10);
  94.   double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  95.   make2(int, n, m);
  96.   RE (i, n) {
  97.     RE (j, m) {
  98.       char c;
  99.       scanf(" %c", &c);
  100.       b[i][j] = c - '0';
  101.       if (b[i][j] == 0) {
  102.         dep[i][j] = 0;
  103.       } else {
  104.         dep[i][j] = 1 + dep[i - 1][j];
  105.       }
  106.     }
  107.   }
  108.  
  109.   RE (i, n) {
  110.     VPII stack;
  111.     stack.PB(MP(0, 0));
  112.     RE (j, m + 1) {
  113.       int last_popped = j;
  114.       while (stack.back().second > dep[i][j]) {
  115.         rec[stack.back().second][j - stack.back().first]++;
  116.         rec[max(stack[stack.size() - 2].second, dep[i][j])][j - stack.back().first]--;
  117.         last_popped = stack.back().first;
  118.         stack.pop_back();
  119.       }
  120.       stack.PB(MP(last_popped, dep[i][j]));
  121.     }
  122.   }
  123.  
  124.   for (int tr = 1; tr <= 2; tr++) {
  125.     RE (i, n) {
  126.       FORD (j, m, 1) {
  127.         rec[i][j] += rec[i][j + 1];
  128.       }
  129.     }
  130.   }
  131.   RE (j, m) {
  132.     FORD (i, n, 1) {
  133.       rec[i][j] += rec[i + 1][j];
  134.     }
  135.   }
  136.   RE (i, n) {
  137.     RE (j, m) {
  138.       cout<<rec[i][j]<<" ";
  139.     }
  140.     cout<<"\n";
  141.   }
  142.  
  143.   return 0;
  144. }
Success #stdin #stdout 0s 97216KB
comments (?)
stdin
copy 
3 3
011
110
110
stdout
copy 
6 3 0 
3 1 0 
1 0 0
https://ideone.com/r37Qxb
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!