# On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.
#
# Initially, some number of lamps are on.  lamps[i] tells us the location of the i-th lamp that is on.  Each lamp
# that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).
#
# For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.
#
# After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x,
# y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)
#
# Return an array of answers.  Each value answer[i] should be equal to the answer of the i-th query queries[i].
#
#
#
# Example 1:
#
# Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
# Output: [1,0]
# Explanation:
# Before performing the first query we have both lamps [0,0] and [4,4] on.
# The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,
# 4] is the bottom right corner:
# 1 1 1 1 1
# 1 1 0 0 1
# 1 0 1 0 1
# 1 0 0 1 1
# 1 1 1 1 1
# Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off,
# and the grid now looks like this:
# 1 0 0 0 1
# 0 1 0 0 1
# 0 0 1 0 1
# 0 0 0 1 1
# 1 1 1 1 1
# Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the
# cell is no longer lit.
#
#
# Note:
#
# 1 <= N <= 10^9
# 0 <= lamps.length <= 20000
# 0 <= queries.length <= 20000
# lamps[i].length == queries[i].length == 2

import collections


class Solution(object):
    def gridIllumination_tle(self, N, lamps, queries):
        """
        :type N: int
        :type lamps: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        grid = [[0] * N for _ in xrange(N)]

        def turnOn(row, col):
            # turn on row
            for j in xrange(N):
                # if j == col:
                #     continue
                grid[row][j] += 1

            # turn on col
            for i in xrange(N):
                # avoid duplicate increments
                if i == row:
                    continue
                grid[i][col] += 1

            for r, c in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
                r0, c0 = row + r, col + c
                while 0 <= r0 < N and 0 <= c0 < N:
                    grid[r0][c0] += 1
                    r0, c0 = r0 + r, c0 + c

        def turnOff(row, col):
            if row + 1 < N:
                grid[row + 1][col] = max(grid[row + 1][col] - 1, 0)
            if row - 1 >= 0:
                grid[row - 1][col] = max(grid[row - 1][col] - 1, 0)
            if col + 1 < N:
                grid[row][col + 1] = max(grid[row][col + 1] - 1, 0)
            if col - 1 >= 0:
                grid[row][col - 1] = max(grid[row][col - 1] - 1, 0)

            # turn off
            for r, c in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
                nRow, nCol = r + row, c + col
                if 0 <= nRow < N and 0 <= nCol < N:
                    grid[nRow][nCol] = max(grid[nRow][nCol] - 1, 0)

        for l in lamps:
            turnOn(l[0], l[1])

        for g in grid:
            print g

        res = []
        for q in queries:
            r, c = q
            if grid[r][c] > 0:
                res.append(1)
            else:
                res.append(0)

            turnOff(r, c)
        return res

    def gridIllumination(self, N, lamps, queries):
        """
        :type N: int
        :type lamps: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        rows, cols, diags, anti_diaogs = collections.Counter(), collections.Counter(), collections.Counter(), \
                                         collections.Counter()
        lights = set()

        for l in lamps:
            # rows and cols counter increment
            rows[l[0]], cols[l[1]] = rows[l[0]] + 1, cols[l[1]] + 1
            # diagnoal and ainti-diagnol
            # for a point in diagnol, (x,y), the next point is (x+1,y+1), the previous is (x-1, y-1)
            # so, we use diags[x-y], notice, we can not use diags[abs(x-y)], it cause error
            # for anti-diagnol, it is (x-1, y+1) or (x+1,y-1), so the sum would always be (x+y)
            # so we use anti-diagnol[x-y] for recording
            diags[l[0] - l[1]] += 1
            anti_diaogs[l[0] + l[1]] += 1
            lights.add((l[0], l[1]))

        res = []
        for q in queries:
            if rows[q[0]] > 0 or cols[q[1]] > 0 or diags[q[0] - q[1]] > 0 or anti_diaogs[q[0] + q[1]] > 0:
                res.append(1)
            else:
                res.append(0)

            # check itself and its adjacent 8 points, to see if there is any one in lights set
            # if there is, we need to remove the counter
            for i in (-1, 0, 1):
                for j in (-1, 0, 1):
                    nq0, nq1 = q[0] + i, q[1] + j
                    if (nq0, nq1) in lights:
                        # don't forget to remove the light from sets
                        lights.discard((nq0, nq1))

                        # turn off all the counter which added by the above light
                        rows[nq0], cols[nq1] = rows[nq0] - 1, cols[nq1] - 1
                        diags[nq0 - nq1] -= 1
                        anti_diaogs[nq0 + nq1] -= 1

        return res


if __name__ == '__main__':
    print Solution().gridIllumination(5, [[0, 0], [4, 4]], [[1, 1], [1, 0]])
    print Solution().gridIllumination(5, [[0, 0], [4, 4]], [[1, 1], [1, 1]])
