Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

There is a square table composed of N*N Cells. Initially all cell is filled with a number 0. Two types of Operations can be performed on the table.

R i k: All the numbers in the cells on ith row has been changed to k.

C i k: All the numbers in the cells on ith column has been changed to k.

Please Note : k ∈ {0, 1} (ie k = 0 or 1).

At any time ,Alice is interested to know the total number of 0's on some row or total number of 0's on some column.

Our task is to answer Alice Query.

Input

First line contains a single integer N as described above.Next line contains a single integer Q representing the total operations and queries from Alice. Then Followed Q lines , containing operations or queries in following format:

R i k: All the numbers in the cells ith row has been changed to k.

C i k: All the numbers in the cells ith column has been changed to k.

qc i :How many 0's are there in ith row?

qr i:How many cols are there in ith col?

Examples: Input:

3

6

qr 1

C 1 1

qr 1

qc 1

R 1 0

qc 1

Output:

3

2

0

1

I tried a Naive solution.But it got time out. The constraint is quite large and the time limit is just 0.55 Seconds.

**1 ≤ N, Q ≤ 500000 (6 * 10^5)

How can i solve this problem within the given time-limit?

P.S: This is not a homework.

share|improve this question
4  
Please give proper credit for the source of the problem. Also, please include some of your own thoughts. Which operations are timed, only queries or also manipulations? –  Raphael Feb 4 '13 at 12:19
2  
@ChopraJack You can use 2 arrays of size $N$, one for cols and the other for rows, in which you store the number of 0's in each col/row. Initially, the array values are set to $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likwise for the i'th row). –  saadtaame Feb 4 '13 at 14:24
    
@saadtaame Turn to an answer? –  Yuval Filmus Feb 4 '13 at 15:45
    
I agreee with @Raphael, OP should state if settings are to be considered for performance or not. If they aren't, saadtaame's solution is as good as it could get. If not... –  vonbrand Feb 4 '13 at 18:55
1  
@Raphael You can't! You still use the grid of zeros and ones. My argument concerns running time. –  saadtaame Feb 5 '13 at 11:15
show 2 more comments

1 Answer

My solution uses 2 arrays (R and C) to store the zero-counts and a 1D array (Grid) to represent the grid of zeros and ones as a sequence of numbers. All 3 arrays are of size $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likewise for the i'th row). Here is a Python implementation and a test case (yours):

N = 3
R = []
C = []
Grid = []

for k in range(N):
    R.append(N)
    C.append(N)
    Grid.append(0)

def qr(k):
    print R[k - 1]

def qc(k):
    print C[k - 1]

def r(i, k):
    R[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[i - 1] & (1 << l) >> l)
        if bit != k:
            if k == 0:
                C[l] = C[l] + 1
            else:
                C[l] = C[l] - 1
        Grid[i - 1] = Grid[i - 1] | (k << l)

def c(i, k):
    C[i - 1] = (1 - k) * N
    for l in range(N):
        bit = ((Grid[l] & (1 << (i - 1))) >> (i - 1))
        if bit != k:
            if k == 0:
                R[l] = R[l] + 1
            else:
                R[l] = R[l] - 1
        Grid[l] = Grid[l] | (k << (i - 1))

qr(1)
c(1, 1)
qr(1)
qc(1)
r(1, 0)
qc(1)

You have to complete this with code that parses the input file and interprets the commands.

share|improve this answer
    
An update operation takes linear time in N.In worst case , updates can be as big as 6 * 10^5. So N*6 * 10^5 is too slow.The Timelimit is just 0.55 Secs –  Chopra Jack Feb 5 '13 at 20:18
    
@ChopraJack True. –  saadtaame Feb 6 '13 at 0:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.