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_back

typedef 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;}

coding problems