Iosif Pinelis proved that, when a solution is guaranteed to exist, it can be found using finitely many queries.
When a solution is not guaranteed to exist, then it may be impossible to decide whether or not it exists with finitely many queries. I could prove it for the special case $t = s$. Suppose that, after some $n$ queries, for every $j\in [n]$, the answer for query $x_j$ is $g(x_j)=x_j$ and the answer for query $y_j$ is $g^{-1}(y_j)=y_j$. Then, it is possible that $g(x)\equiv x$, in which case no solution exists. However, it is also possible that $g(x)$ is slightly different than $x$ in some open interval that does not contain any $x_j$ or $y_j$. In this case a solution exists.
When $t<s$ and a solution is not guaranteed to exist, Iosif Pinelis proved that the problem may not be decided using a finite number of non-adaptive queries (queries that must be determined in advance, and may not depend on answers to previous queries). The idea is that, for every finite number $n$ of queries, there is a piecewise-linear function $g$ for which no solution exists, and a slight modification of it - that does not change the answer to any of the $n$ queries - yields a function $h$ for which a solution exists.
A remaining open case is that of adaptive queries, in which each query may depend on answers to previous queries. When $t<s$, I do not know if it is possible to decide with finitely-many queries.