Integer solution For every prime $p$, does there exists integers $x_1$, $x_2$ and $x_3$ ($0\leq x_1, x_2, x_3 \leq \lfloor cp^{1/3}\rfloor$ and $c$ is some large constant) such that $\frac{p-1}{2}-\lfloor 2cp^{1/3} \rfloor \leq f(x_1,x_2,x_3) \leq \frac{p-1}{2}$, where, $f(x_1,x_2,x_3)=x_1+x_2+x_3+2(x_1x_2+x_2x_3+x_3x_1)+4x_1x_2x_3$.

I doubt that the lower bound $\frac{p-1}{2} - 2cp^{1/3}$ holds for all $p$. Here is a proof for the weaker bound $\frac{p-1}{2} - cp^{1/2}$. 
First of all, the inequality $\frac{p-1}{2}-cp^{1/2} \leq f(x_1,x_2,x_3) \leq \frac{p-1}{2}$ is essentially equivalent to
$$p- O(p^{1/2}) \leq (2x_1+1)(2x_2+1)(2x_3+1) \leq p.$$
Let us take $y=\left\lceil\frac{p^{1/3}-1}{2}\right\rceil$. Then 
$$p \leq (2y+1)^3 < (p^{1/3}+2)^3 < p + O(p^{2/3}).$$
Define 
$$z = \left( \frac{(2y+1)^3 - p}{4(2y+1)} \right)^{1/2} .$$
Clearly, we have $z=O(p^{1/6})$.
Now, let us take $x_1 = y$, $x_2 = y - \lceil z\rceil$, $x_3 = y + \lceil z\rceil$ so that
$$(2x_1+1)(2x_2+1)(2x_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1)$$
$$ < (2y+1)^3 - 4z^2(2y+1) = p.$$
On the other hand, we have
$$(2x_1+1)(2x_2+1)(2x_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1) $$
$$ > (2y+1)^3 - 4(z+1)^2(2y+1) = p - O(p^{1/2}).$$
