No.2974 Germs of Functions
p-adic
hiro1729
binapProblem Statement
First, we introduce some terminology. Let $f(x)$ and $g(x)$ be real-valued functions whose domain is the set of all real numbers, and let $x_0$ be a real number. We say that $f(x)$ and $g(x)$ coincide in a neighborhood of $x = x_0$ if there exists a positive real number $\delta$ satisfying the following condition:
- For any real number $x$ satisfying $|x - x_0| < \delta$, we have $f(x) = g(x)$.
Roughly speaking, this means that the values of $f(x)$ and $g(x)$ coincide when restricted to a sufficiently small neighborhood of $x_0$.
A positive integer $Q$ is given at the beginning of the input.
You are given $2$ real-valued functions $F(x)$ and $G(x)$ whose domain is the set of all real numbers, both of which are constant functions identically equal to $0$.
Process the $Q$ queries described below in the given order.
Each query is a tuple $(K,L,M,N,X)$ of $5$ integers $K, L, M, N, X$.
A query $(K,L,M,N,X)$ is processed as follows:
- First, update the function $F(x)$ by replacing it with the function obtained by adding $\max \{0,Kx+L\}$ to it.
- Next, update the function $G(x)$ by replacing it with the function obtained by adding $\max \{0,Mx+N\}$ to it.
- Finally, for the updated $F(x)$ and $G(x)$, determine whether the proposition "$F(x)$ and $G(x)$ coincide in a neighborhood of $x = X$" is true or false. (Hereafter, this truth value is called the answer to this query.)
Background
This section explains the background for those familiar with the theory of germs. Let $f(x)$ and $g(x)$ be real-valued functions whose domain is the set of all real numbers, and let $x_0$ be a real number. The statement that $f(x)$ and $g(x)$ coincide in a neighborhood of $x = x_0$ means precisely that the germs of $f(x)$ and $g(x)$ at $x = x_0$ coincide. In other words, this problem is equivalent to the problem of determining whether germs of functions coincide.
The concept of a germ is defined not only for functions but also for the more general concept of sections of a sheaf. Germs of functions are mainly used in analysis, complex geometry, and similar fields, while germs of sections of sheaves play a very important role in algebraic geometry, category theory, and similar fields.
Input
For each positive integer $q$ not exceeding $Q$, the $q$-th query is denoted by $(K_q,L_q,M_q,N_q,X_q)$.
The input is then given from standard input in $1 + Q$ lines in the following format:
- Line $1$ contains $Q$.
- For each positive integer $q$ not exceeding $Q$, line $1+q$ contains the components of the $q$-th query $(K_q,L_q,M_q,N_q,X_q)$, separated by single-byte spaces.
$Q$ $K_1$ $L_1$ $M_1$ $N_1$ $X_1$ $\vdots$ $K_Q$ $L_Q$ $M_Q$ $N_Q$ $X_Q$
Constraints
The input satisfies the following constraints:
- $Q$ is an integer satisfying $1 \leq Q \leq 10^5$
- For any positive integer $q$ not exceeding $Q$,
- $K_q$ is an integer satisfying $-10^9 \leq K_q \leq 10^9$
- $L_q$ is an integer satisfying $-10^9 \leq L_q \leq 10^9$
- $M_q$ is an integer satisfying $-10^9 \leq M_q \leq 10^9$
- $N_q$ is an integer satisfying $-10^9 \leq N_q \leq 10^9$
- $X_q$ is an integer satisfying $-10^9 \leq X_q \leq 10^9$
Output
For each positive integer $q$ not exceeding $Q$, if the answer to the $q$-th query is true, print Yes, and if it is false, print No, on line $q$.
Print a newline at the end.
Sample
Sample 1
Input
1 0 1 1 0 0
Output
No
Initially, $F(x)$ and $G(x)$ are given as constant functions taking only the value $0$.
By the query $(K_1,L_1,M_1,N_1,X_1) = (0,1,1,0,0)$, $F(x)$ and $G(x)$ are replaced by
$\displaystyle \begin{array}{rclclcl} \displaystyle F(x) &\displaystyle = &\displaystyle 0 + \max \{0,K_1 x+L_1\} &\displaystyle = &\displaystyle 0 + \max \{0,1\} &\displaystyle = &\displaystyle 1 \\ \displaystyle G(x) &\displaystyle = &\displaystyle 0 + \max \{0,M_1x+N_1\} &\displaystyle = &\displaystyle 0 + \max \{0,x\} &\displaystyle = &\displaystyle \max \{0,x\} \end{array} $
. For the updated $F(x)$ and $G(x)$,
$\displaystyle \begin{array}{rclcl} \displaystyle F(X_1) &\displaystyle = &\displaystyle F(0) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(X_1) &\displaystyle = &\displaystyle G(0) &\displaystyle = &\displaystyle 0 \end{array} $
holds, so $F(X_1) \neq G(X_1)$; in particular, no matter how small a neighborhood of $X_1$ is taken, the restrictions of $F(x)$ and $G(x)$ do not coincide. Since $Q = 1$ here, all queries have now been processed.
Sample 2
Input
1 0 1 1 0 1
Output
No
The only difference from Sample 1 is the $X_1$ part of the query. Therefore, the updated $F(x)$ and $G(x)$ are
$\displaystyle \begin{array}{rcl} \displaystyle F(x) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(x) &\displaystyle = &\displaystyle \max \{0,x\} \end{array} $
. This time,
$\displaystyle \begin{array}{rclcl} \displaystyle F(X_1) &\displaystyle = &\displaystyle F(1) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(X_1) &\displaystyle = &\displaystyle G(1) &\displaystyle = &\displaystyle 1 \end{array} $
holds, so $F(X_1) = G(X_1)$. However, no matter how small a positive real number $\delta$ is taken, at $x = X_1 + 2^{-1} \delta$ we have $|x - X_1| = 2^{-1} \delta < \delta$ and
$\displaystyle \begin{array}{rclcl} \displaystyle F(x) &\displaystyle = &\displaystyle F(1 + 2^{-1} \delta) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(x) &\displaystyle = &\displaystyle G(1 + 2^{-1} \delta) &\displaystyle = &\displaystyle 1 + 2^{-1} \delta \end{array} $
, so $F(x) \neq G(x)$. That is, no matter how small a neighborhood of $X_1$ is taken, the restrictions of $F(x)$ and $G(x)$ do not coincide. Since $Q = 1$ here, all queries have now been processed.
Sample 3
Input
2 2 0 2 -1 -2 -1 -1 0 1 1
Output
Yes Yes
Initially, $F(x)$ and $G(x)$ are given as constant functions taking only the value $0$.
By the $1$-st query $(K_1,L_1,M_1,N_1,X_1) = (2,0,2,-1,-2)$, $F(x)$ and $G(x)$ are replaced by
$\displaystyle \begin{array}{rclclcl} \displaystyle F(x) &\displaystyle = &\displaystyle 0 + \max \{0,K_1x+L_1\} &\displaystyle = &\displaystyle 0 + \max \{0,2x\} &\displaystyle = &\displaystyle \max \{0,2x\} \\ \displaystyle G(x) &\displaystyle = &\displaystyle 0 + \max \{0,M_1x+N_1\} &\displaystyle = &\displaystyle 0 + \max \{0,2x-1\} &\displaystyle = &\displaystyle \max \{0,2x-1\} \end{array} $
. Noting that both the updated $F(x)$ and $G(x)$ take the value $0$ if $x < 0$, if we set for example $\delta = 2$, then for any real number $x$ satisfying $|x - X_1| < \delta$, we have $x < X_1 + \delta = 0$ and hence $F(x) = G(x)$.
By the $2$-nd query $(K_2,L_2,M_2,N_2,X_2) = (-1,-1,0,1,1)$, $F(x)$ and $G(x)$ are replaced by
$\displaystyle \begin{array}{rclclcl} \displaystyle F(x) &\displaystyle = &\displaystyle \max \{0,2x\} + \max \{0,K_2x+L_2\} &\displaystyle = &\displaystyle \max \{0,2x\} + \max \{0,-x-1\} &\displaystyle = &\displaystyle \max \{0,2x,-x-1,x-1\} \\ \displaystyle G(x) &\displaystyle = &\displaystyle \max \{0,2x-1\} + \max \{0,M_2x+N_2\} &\displaystyle = &\displaystyle \max \{0,2x-1\} + \max \{0,1\} &\displaystyle = &\displaystyle \max \{1,2x\} \end{array} $
. If we set $\delta = \frac{1}{2}$, then for any real number $x$ satisfying $|x - X_2| < \delta$, we have $\frac{1}{2} < x < \frac{3}{2}$, and therefore
$\displaystyle \begin{array}{lclcl} \displaystyle 2x - 0 &\displaystyle = &\displaystyle 2x &\displaystyle > &\displaystyle 0 \\ \displaystyle 2x - (-x-1) &\displaystyle = &\displaystyle 3x+1 &\displaystyle > &\displaystyle 0 \\ \displaystyle 2x - (x-1) &\displaystyle = &\displaystyle x+1 &\displaystyle > &\displaystyle 0 \\ \displaystyle 2x - 1 &\displaystyle &\displaystyle &\displaystyle > &\displaystyle 0 \end{array} $
holds, so $F(x) = 2x$ and $G(x) = 2x$, that is, $F(x) = G(x)$. Since $Q = 2$ here, all queries have now been processed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。