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