Univariate polynomials
Given $n$, is there a degree $cn^{c'}$ polynomial $p(x)\in\Bbb R[x]$ and a degree $dn^{d'}$ polynomial $q(x)\in\Bbb R[x]$ with fixed $c,c',d,d'>0$ such that $$m\in\Bbb Z:|2m|<2^n\implies p(2m)=0\mbox{ and }p(2m+1)\neq0$$$$m\in\Bbb Z:|2m|<2^n\implies q(2m)\neq0 \mbox{ and }q(2m+1)=0?$$
For the first pair of conditions: $p(x)$ would be divisible by the polynomial $$x\prod_{m=1}^{2^{n-1}-1}(x^2-4m^2).$$ Indeed, the first condition gives a list of zeroes: $0,2,4, \dots 2m,\dots,2^{n}-2$ and their opposites. This means the polynomial is divisible by each of $x\pm 2m$, hence by their product, since any pair of these are coprime.
The degree of the latter polynomial is $2^n-1$, so the answer is
no.Similarly, for the second pair of conditions, the degree can't be $O(n^d)$ since it would be (at least) exponential in $n$.