Advertisement
Guest User

Untitled

a guest
Apr 6th, 2020
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. #define NguyenDangQuan the_author
  2.  
  3. #include <bits/stdc++.h>
  4. #define all(x) x.begin(),x.end()
  5. #define mset(x, i) memset(x,i,sizeof(x))
  6. #define elif else if
  7. #define heap priority_queue
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define ld long double
  12. #define ll long long
  13. #define ull unsigned long long
  14. #define task ""
  15. using namespace std;
  16.  
  17. int typetest;
  18. template<class T>
  19. void read(T &x){
  20.     register int c;
  21.     T neg = 1;
  22.     x = (T)0;
  23.     while ((c = getchar()) <= 47 || c >= 58)
  24.         if(c == '-') neg = -1;
  25.     for (; (c > 47 && c < 58); c = getchar()){
  26.         x = (x << 3) + (x << 1) + (T)(c - 48);
  27.     }
  28.     x *= neg;
  29. }
  30. inline void fastIOfileinput(){
  31.     ios_base:: sync_with_stdio(0);
  32.     cin.tie(0);
  33.     cout.tie(0);
  34. //  freopen(task".INP", "r", stdin);
  35. //  freopen(task".OUT", "w", stdout);
  36. //  freopen(task".in", "r", stdin);
  37. //  freopen(task".out", "w", stdout);
  38.     typetest = 0;
  39. }
  40.  
  41. struct quan{
  42.     int val, l, r;
  43.     quan() {}
  44.     quan(int u, int v, int k){
  45.         val = u;
  46.         l = v;
  47.         r = k;
  48.     }
  49. };
  50.  
  51. const int N = 3e2 + 2;
  52. const int M = 1e6 + 2;
  53. int m, n, a[N][N], b[N][N], c[N][N];
  54. vector<quan> s;
  55.  
  56. void Enter(){
  57.     read(m); read(n);
  58.     for(int i = 1; i <= m; ++i)
  59.         for(int j = 1; j <= n; ++j)
  60.             read(c[i][j]);
  61. }
  62.  
  63. void quaylui(int x, int y, int h){
  64.     if(x == y){
  65.         int u = s[x].r - s[x].l + 1;
  66.         for(int i = h + 1; i <= s[x].val; ++i)
  67.             for(int j = 1; j <= u; ++j)
  68.                 b[i][j] += u - j + 1;
  69.         return;
  70.     }
  71.     if(x > y)
  72.         return;
  73.     int minn = 1e5;
  74.     int u = s[y].r - s[x].l + 1;
  75.     for(int i = x; i <= y; ++i)
  76.         if(minn > s[i].val)
  77.             minn = s[i].val;
  78.     for(int i = h + 1; i <= minn; ++i)
  79.         for(int j = 1; j <= u; ++j)
  80.                 b[i][j] += u - j + 1;
  81.     for(int i = x - 1; i <= y; ++i){
  82.         if(s[i].val == minn || i == x - 1){
  83.             int j = i + 1;
  84.             while(j <= y && s[j].val > minn)
  85.                 ++j;
  86.             quaylui(i + 1, j - 1, minn);
  87.             i = j - 1;
  88.         }
  89.     }
  90. }
  91.  
  92. void solve(){
  93.     mset(b, 0);
  94.     int f[N];
  95.     mset(f, 0);
  96.     for(int i = 1; i <= m; ++i){
  97.         s.clear();
  98.         for(int j = 1; j <= n; ++j)
  99.             if(c[i][j] == 0) ++f[j];
  100.             else f[j] = 0;
  101.         for(int j = 1; j <= n; ++j){
  102.             int v = j;
  103.             while(v <= n && f[v] == f[j])
  104.                 ++v;
  105.             s.pb(quan(f[j], j, v - 1));
  106.             j = v - 1;
  107.         }
  108.         quaylui(0, s.size() - 1, 0);
  109.     }
  110.     for(int i = 1; i <= m; ++i)
  111.         for(int j = 1; j <= n; ++j)
  112.             cout << b[i][j] << (j == n ? "\n" : " ");
  113. }
  114.  
  115. signed main(){
  116.     fastIOfileinput();
  117.     if(typetest){
  118.         int t;
  119.         cin >> t;
  120.         while(t--){
  121.             Enter();
  122.             solve();
  123.         }
  124.     }
  125.     else{
  126.         Enter();
  127.         solve();
  128.     }
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement