HackerEarth Frames problem solution

In this HackerEarth Frames problem solution, You are given a NxM matrix consisting of 0s and 1s. Find the number of square frames with no 1s (each cell is 0) in this matrix. A frame of a fixed square is a group of cells each of them is one of the leftmost, rightmost, topmost or bottommost cells. Thus a square frame with the side length 1 contains 1 cell, with the side length 2 contains 4, with the side length 3 - 8 cells, with the side length 4 - 12 cells.

HackerEarth Frames problem solution.

`#include <cstdio>#include <algorithm>#include <vector>#include <iostream>#include <set>#include <map>#include <iomanip>#include <string>#include <string.h>#include <cstdlib>#include <bitset>#include <cmath>#include <random>#define X first#define Y second#define mp make_pair#define pb push_backtypedef long long ll;using namespace std;int n, m;int a[2010][2010];int up[2010][2010], lft[2010][2010], rght[2010][2010], down[2010][2010];int r[5010];void modify(int x, int y) {    for (; x < 5010; x = (x|(x+1))) {        r[x] += y;    }}int query(int x) {    int res = 0;    for (; x >= 0; x = ((x&(x+1))-1) ) {        res += r[x];    }    return res;}int sum(int l, int r) {    if (l > r) {        return 0;    }    return query(r) - query(l-1);}vector<int>del[5010];int main() {    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++) {        char s[2010];        scanf("%s", s);        for (int j = 1; j <= m; j++) {            a[i][j] = s[j-1] - '0';        }    }    for (int i = n; i > 0; i--) {        for (int j = 1; j <= m; j++) {            if (a[i][j] == 1) {                up[i][j] = 0;            }            else {                up[i][j] = up[i+1][j] + 1;            }        }    }    for (int i = n; i > 0; i--) {        for (int j = 1; j <= m; j++) {            if (a[i][j] == 1) {                lft[i][j] = 0;            }            else {                lft[i][j] = lft[i][j-1] + 1;            }        }    }    for (int i = n; i > 0; i--) {        for (int j = m; j >= 0; j--) {            if (a[i][j] == 1) {                rght[i][j] = 0;            }            else {                rght[i][j] = rght[i][j+1] + 1;            }        }    }    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= m; j++) {            if (a[i][j] == 1) {                down[i][j] = 0;            }            else {                down[i][j] = down[i-1][j] + 1;            }        }    }    long long ans = 0;    for (int i = 1; i <= n; i++) {        memset(r, 0, sizeof(r));        for (int j = 0; j < 5010; j++) {            del[j].clear();        }        int x = i, y = 1;        while (x <= n && y <= m) {            int uprght = min(up[x][y], rght[x][y]);            del[y + uprght].push_back(y);            modify(y, 1);            for (int j = 0; j < del[y].size(); j++) {                modify(del[y][j], -1);            }            int downlft = min(down[x][y], lft[x][y]);            ans += sum(y - downlft + 1, y);            x++; y++;        }    }    for (int i = 2; i <= m; i++) {        memset(r, 0, sizeof(r));        for (int j = 0; j < 5010; j++) {            del[j].clear();        }        int x = 1, y = i;        while (x <= n && y <= m) {            int uprght = min(up[x][y], rght[x][y]);            del[x + uprght].push_back(x);            modify(x, 1);            for (int j = 0; j < del[x].size(); j++) {                modify(del[x][j], -1);            }            int downlft = min(down[x][y], lft[x][y]);            ans += sum(x - downlft + 1, x);            x++; y++;        }    }    cout<<ans<<endl;    return 0;}`

Second solution

`#include <bits/stdc++.h>using namespace std;long n,m,d[2050][2050],u[2050][2050],l[2050][2050],r[2050][2050],ul[2050][2050],dr[2050][2050],t[2050];string st;long long ans;long board[2050][2050];vector<long> event[2050];void add(long ps,long val){     for(;ps<=n;ps=(ps|(ps+1)))      t[ps]+=val;}long sum(long r){ long res=0; for(;r>=0;r=(r&(r+1))-1)  res+=t[r]; return res;}long sum(long l,long r){ return sum(r)-sum(l-1);}int main(){ios_base::sync_with_stdio(0);cin>>n>>m;for (int i=0;i<=n+1;i++) for (int j=0;j<=m+1;j++)  board[i][j]=1;  for (int i=1;i<=n;i++){ cin>>st; for (int j=1;j<=m;j++)  board[i][j]=st[j-1]-48;}for (int i=n;i;--i) for (int j=m;j;--j) {  r[i][j]=r[i][j+1]+1;  d[i][j]=d[i+1][j]+1;  if (board[i][j]==1)   r[i][j]=d[i][j]=0; }for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {  u[i][j]=u[i-1][j]+1;  l[i][j]=l[i][j-1]+1;  if (board[i][j]==1)   u[i][j]=l[i][j]=0; }for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) {  ul[i][j]=min(u[i][j],l[i][j]);  dr[i][j]=min(d[i][j],r[i][j]);    }  ans=0;for (int Dif=-n-m;Dif<=n+m;Dif++){    for (int i=1;i<=n;i++)     event[i].clear();         for (int i=0;i<=n;i++)     t[i]=0;         for (int i=1;i<=n;i++)    {     for (int j=0;j<event[i].size();j++)     {         long ps=event[i][j];         add(ps,-1);        }          long j=i+Dif;     if (j<1||j>m)continue;     if (board[i][j])continue;     add(i,1);     long q=dr[i][j];     if (i+q<=n)      event[i+q].push_back(i);     q=ul[i][j];     ans+=sum(i-q+1,i);     }     }cout<<ans<<endl;cin.get();cin.get();return 0;}`