Problem M
Umbral Decoding
You are planning a clever attack against a new encryption algorithm. To succeed, you need to find the key, which is a pair of integers $(p, q)$. We can think of the key as a point on a two-dimensional integer lattice whose location is unknown. However, you know that $(p, q)$ lies in the square spanned by the lattice points $(0, 0)$ and $(n, n)$ for a given $n$, i.e. $0\leq p,q\leq n$.
Your attack has three stages:
-
Identify safe points and their bounds.
-
Eliminate as key candidates those points that lie in the “umbra” of any safe point.
-
Test the remaining points to see which one is the key.
Stage 1 has already been performed and you are given several safe points of the form $(x, y, b)$ as input.
In Stage 2 you eliminate a point $(p, q)$ if it lies in the umbra of any safe point. Point $(p, q)$ is in the umbra of safe point $(x, y, b)$ if and only if
\[ |x-p|^3 + |y-q|^3 \leq b. \]Your task in this problem is to count how many points will be left for testing in Stage 3 so that we have an estimate of the amount of work left to complete the attack.
Input
Input begins with two integers $n, k$ on a single line, separated by a space, with $2 \leq n \leq 100\, 000\, 000$, and $0 \leq k \leq 100$. Following that are $k$ lines each containing three integers $x, y, b$ separated by spaces, representing the safe points. The values of $x$ and $y$ are both in the range $[0,n]$. The bound $b$ lies in the range $[0, n]$.
Output
Output the number of points $(p, q)$, with $0 \leq p,q \leq n$, that do not lie in the umbra of any safe point.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 2 2 2 |
16 |
Sample Input 2 | Sample Output 2 |
---|---|
30 2 20 20 30 25 22 30 |
891 |