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