CCC '21 S2 - Modern Art - Olympiads Online Judge

CCC '21 S2 - Modern Art

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 1G

Problem type

Canadian Computing Competition: 2021 Stage 1, Junior #5, Senior #2

A new and upcoming artist has a unique way to create checkered patterns. The idea is to use an $M$ $M$ -by- $N$ $N$ canvas which is initially entirely black. Then the artist repeatedly chooses a row or column and runs their magic brush along the row or column. The brush changes the colour of each cell in the row or column from black to gold or gold to black. Given the artist's choices, your job is to determine how much gold appears in the pattern determined by these choices.

Input Specification

The first line of input will be a positive integer $M$ $M$ . The second line of input will be a positive integer $N$ $N$ . The third line of input will be a positive integer $K$ $K$ . The remaining input will be $K$ $K$ lines giving the choices made by the artist. Each of these lines will either be R followed by a single space and then an integer which is a row number, or C followed by a single space and then an integer which is a column number. Rows are numbered top down from $1$ $1$ to $M$ $M$ . Columns are numbered left to right from $1$ $1$ to $N$ $N$ .

The following table shows how the available $15$ $15$ marks are distributed.

Subtask	$M$ $M$	$N$ $N$	$K$ $K$	Description
$1$ $1$ mark	$M = 1$ $M = 1$	$N = 1$ $N = 1$	$K \le 100$ $K \leq 100$	only one cell, and up to $100$ $100$ choices by the artist
$4$ $4$ marks	$M = 1$ $M = 1$	$N \le 100$ $N \leq 100$	$K \le 100$ $K \leq 100$	only one row, and up to $100$ $100$ choices by the artist
$5$ $5$ marks	$M \le 100$ $M \leq 100$	$N \le 100$ $N \leq 100$	$K \le 100$ $K \leq 100$	up to $100$ $100$ rows, up to $100$ $100$ columns, and up to $100$ $100$ choices by the artist
$5$ $5$ marks	$MN \le 5\,000\,000$ $M N \leq 5 000 000$		$K \le 1\,000\,000$ $K \leq 1 000 000$	up to $5\,000\,000$ $5 000 000$ cells, and up to $1\,000\,000$ $1 000 000$ choices by the artist

Output Specification

Output one non-negative integer which is equal to the number of cells that are gold in the pattern determined by the artist's choices.

Sample Input 1

Copy

Output for Sample Input 1

Copy

Explanation of Output for Sample Input 1

After running the brush along the first row, the canvas looks like this:

Copy

GGG
BBB
BBB

Then after running the brush along the first column, four cells are gold in the final pattern determined by the artist's choices:

Copy

BGG
GBB
GBB

Sample Input 2

Copy

4
5
7
R 3
C 1
C 2
R 2
R 2
C 1
R 4

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

Ten cells are gold in the final pattern determined by the artist's choices:

Copy

BGBBB
BGBBB
GBGGG
GBGGG

Comments

4

Hiccup172 commented on Oct. 21, 2024, 4:08 a.m. ← edit 3 →

Small hint that i think people may need, for the last cases you would need to think outside the box to make it in the time limit, instead of changing the graph think about the amount of changes you need to make this.

R 1

R 1

=

R 0

think about that as a hint so for time don't think 2d array think 2 arrays.

0

PHo3NIX commented 56 days ago

really useful and thank u. I've been thinking about this problem for a long time. lol

2

Someone_you_can_trust commented on April 3, 2021, 12:49 a.m.

Is this possible in python ?

3

BalintR commented on April 3, 2021, 1:46 a.m.

Yes https://dmoj.ca/problem/ccc21s2/rank/?language=PY2&language=PY3&language=PYPY&language=PYPY3