Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define NguyenDangQuan the_author
- #include <bits/stdc++.h>
- #define all(x) x.begin(),x.end()
- #define mset(x, i) memset(x,i,sizeof(x))
- #define elif else if
- #define heap priority_queue
- #define fi first
- #define se second
- #define pb push_back
- #define ld long double
- #define ll long long
- #define ull unsigned long long
- #define task ""
- using namespace std;
- int typetest;
- template<class T>
- void read(T &x){
- register int c;
- T neg = 1;
- x = (T)0;
- while ((c = getchar()) <= 47 || c >= 58)
- if(c == '-') neg = -1;
- for (; (c > 47 && c < 58); c = getchar()){
- x = (x << 3) + (x << 1) + (T)(c - 48);
- }
- x *= neg;
- }
- inline void fastIOfileinput(){
- ios_base:: sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- // freopen(task".INP", "r", stdin);
- // freopen(task".OUT", "w", stdout);
- // freopen(task".in", "r", stdin);
- // freopen(task".out", "w", stdout);
- typetest = 0;
- }
- struct quan{
- int val, l, r;
- quan() {}
- quan(int u, int v, int k){
- val = u;
- l = v;
- r = k;
- }
- };
- const int N = 3e2 + 2;
- const int M = 1e6 + 2;
- int m, n, a[N][N], b[N][N], c[N][N];
- vector<quan> s;
- void Enter(){
- read(m); read(n);
- for(int i = 1; i <= m; ++i)
- for(int j = 1; j <= n; ++j)
- read(c[i][j]);
- }
- void quaylui(int x, int y, int h){
- if(x == y){
- int u = s[x].r - s[x].l + 1;
- for(int i = h + 1; i <= s[x].val; ++i)
- for(int j = 1; j <= u; ++j)
- b[i][j] += u - j + 1;
- return;
- }
- if(x > y)
- return;
- int minn = 1e5;
- int u = s[y].r - s[x].l + 1;
- for(int i = x; i <= y; ++i)
- if(minn > s[i].val)
- minn = s[i].val;
- for(int i = h + 1; i <= minn; ++i)
- for(int j = 1; j <= u; ++j)
- b[i][j] += u - j + 1;
- for(int i = x - 1; i <= y; ++i){
- if(s[i].val == minn || i == x - 1){
- int j = i + 1;
- while(j <= y && s[j].val > minn)
- ++j;
- quaylui(i + 1, j - 1, minn);
- i = j - 1;
- }
- }
- }
- void solve(){
- mset(b, 0);
- int f[N];
- mset(f, 0);
- for(int i = 1; i <= m; ++i){
- s.clear();
- for(int j = 1; j <= n; ++j)
- if(c[i][j] == 0) ++f[j];
- else f[j] = 0;
- for(int j = 1; j <= n; ++j){
- int v = j;
- while(v <= n && f[v] == f[j])
- ++v;
- s.pb(quan(f[j], j, v - 1));
- j = v - 1;
- }
- quaylui(0, s.size() - 1, 0);
- }
- for(int i = 1; i <= m; ++i)
- for(int j = 1; j <= n; ++j)
- cout << b[i][j] << (j == n ? "\n" : " ");
- }
- signed main(){
- fastIOfileinput();
- if(typetest){
- int t;
- cin >> t;
- while(t--){
- Enter();
- solve();
- }
- }
- else{
- Enter();
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement