(Analysis by Dhruv Rohatgi )

Let's add the cows one by one into a $1000 \times 1000$ boolean array $A$, where a $1$ in position $A[x][y]$ indicates that there is a cow at $(x,y)$, and otherwise $A[x][y] = 0$.

When a new cow is added, there are at most five cows who might either become comfortable or become uncomfortable: the new cow, plus any neighbors she might have. So before adding a cow into position $(x,y)$, we can count the number of neighbors who are comfortable; after adding we count the number of neighbors (or the new cow) who are comfortable, and we update a running counter (of comfortable cows) by the difference.

To make the code simpler, it helps to have a function which, given a position in the array, determines whether there is a comfortable cow at this location.

This algorithm runs in linear time, with only one pass through the input.

#include <iostream>
using namespace std;
#define MAXN 1001

int N;
bool A[MAXN][MAXN];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

bool valid_position(int x,int y)
{
return x>=0 && x<=N && y>=0 && y<=N;
}

bool comfortable(int x,int y)
{
if(A[x][y] == 0) return 0;
int neighbors = 0;
for(int d=0;d<4;d++)
if(valid_position(x+dx[d],y+dy[d]))
if(A[x+dx[d]][y+dy[d]])
neighbors++;
return neighbors == 3;
}

int main()
{
int x,y;
cin >> N;
int nComfortable = 0;
for(int i=0;i<N;i++)
{
cin >> x >> y;
for(int d=0;d<4;d++)
if(valid_position(x+dx[d],y+dy[d]))
nComfortable -= comfortable(x+dx[d],y+dy[d]);
A[x][y] = 1;
for(int d=0;d<4;d++)
if(valid_position(x+dx[d],y+dy[d]))
nComfortable += comfortable(x+dx[d],y+dy[d]);
nComfortable += comfortable(x,y);
cout << nComfortable << '\n';
}
}