COCI '15 Contest 1 #4 Topovi

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Mirko is a huge fan of chess and programming, but typical chess soon became boring for him, so he started having fun with rook pieces.

He found a chessboard with N rows and N columns and placed K rooks on it.

Mirko's game is made of the following rules:

  1. Each rook's power is determined by an integer.
  2. A rook sees all the fields that are in his row or column except its own field.
  3. We say that a field is attacked if the binary XOR of all the powers of the rooks that see the field is greater than 0.

Notice that the field a rook is at can be attacked or not.

Initially, Mirko placed the rooks in a certain layout on the board and will make P moves.

After each move, determine how many fields are attacked.

Every rook can be moved to any free field on the whole board (not only across column and row).

Input Specification

The first line of input contains integers N, K, P (1 \le N \le 1\,000\,000\,000, 1 \le K \le 100\,000, 1 \le P \le 100\,000).

Each of the following K lines contains three integers R, C, X (1 \le R, C \le N, 1 \le X \le 1\,000\,000\,000) which denote that initially there is a rook of power X on the field (R, C).

Each of the following P lines contains four integers R_1, C_1, R_2, C_2 (1 \le R_1, C_1, R_2, C_2 \le N) which denote that the rook has moved from field (R_1, C_1) to field (R_2, C_2).

It is guaranteed that there will not be two rooks on one field at any point.

In test cases worth 25% of total points, N and K will not exceed 100.

Output Specification

The output must consist of P lines, the k^{th} line containing the total number of attacked fields after k moves.

Sample Input 1

2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

Sample Output 1


Explanation for Sample Output 1

After the first move, every field on the board is attacked. For example, field (1, 1) is seen by only one rook so the total XOR for that field is 1. After the second move none of the fields are attacked. For example, field (1, 1) is seen by both rooks so the total XOR for that field is 0.

Sample Input 2

2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

Sample Output 2


Sample Input 3

3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2

Sample Output 3



There are no comments at the moment.