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


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