25203번 - Squirrel 서브태스크다국어

You are in the upper-left corner in a M × N network of trees, at coordinates (1,1). A squirrel jumps from tree to tree. Being a computer science squirrel, it jumps such that it creates fractal patterns of... trees, of course! The S fractals look like the ones in the pictures:

The squirrel follows the following rules:

• The squirrel starts at a given tree
• It then jumps to the north P trees, where P is a given power of two
• It then jumps on two diagonals of length P/2
• It then jumps forming four fractals of size P/2
• It continues on until it creates fractals of size 1
• The pictures show the first four fractals of sizes 1, 2, 4 and 8

The squirrel keeps jumping until it finishes one fractal shape, then it starts again with the next fractal. In how many of the trees can you see the squirrel?

The first line has three integers, M, N, and F. The following F lines describe F fractals. Each line has three integers, the coordinates of the starting tree, followed by the fractal size.

Print one integer, the number of positions where you can see the squirrel.

• You can see the squirrel if there is no tree directly between you and the squirrel's tree.
• The squirrel stops jumping in the current fractal when it finishes all jumps, then starts the next fractal
• The squirrel will never jump at (1,1), where you are.
• The squirrel will never jump outside the network of trees.
• If the squirrel jumps multiple times on the same tree and the tree is visible, then it will be counted multiple times towards the end result.
• 2 ≤ M, N ≤ 50,000
• 1 ≤ F ≤ 1000
• 1 ≤ fractal size ≤ 1024, fractal size is a power of two
• The total number of jumps is at most 300 million

The example corresponds to:

• The tree grid has 14 rows and 20 columns
• The squirrel jumps three fractals, black, red and green
• The triangles mark the starting points of the fractals
• The circles mark the trees that are visible from coordinates (1, 1)
• The thicker circles mark the trees that are visible, where the squirrel jumps multiple times
• The total number of jumps in visible trees is 35