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][1] 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.


  [1]: https://mathoverflow.net/a/371124/34461