Subtask 1: $Q\leq 1000$, $t\leq 100$

Let $f(i,t)$ denote the position of cow $i$ at time $t$. Cow $i$ first joins the line at time $t=i$ at position $i$. At times $i\leq t\leq 2i-1$, cow $i$ does not move. At every time $t\geq 2i$, cow $i$ either moves forward one position in line or moves to position $\left\lfloor\frac{t}{2}\right\rfloor$. This means we have the following recursive formula for $f(i,t)$:

We can directly compute the values of the sequence with this recursion and check whether $l_2\leq f(i,t)\leq r_2$ for each $l_1\leq i\leq r_1$.

Subtask 2: $l_1=r_1$

We need a faster method to compute $f(i,t)$ for large $t$. In this subtask, we only need to compute $f(i,t)$ for one value $i=l_1=r_1$. We can speed up the calculation by observing that if $f(i,t')=0$, then $f(i,t'+1)=\left\lfloor\frac{t'+1}{2}\right\rfloor$, so $f(i,t'+1+k)=\left\lfloor\frac{t'+1}{2}\right\rfloor-k$ for all $0\leq k\leq\left\lfloor\frac{t'+1}{2}\right\rfloor$. This means that the next time which satisfies $f(i,t)=0$ is $t'+1+\left\lfloor\frac{t'+1}{2}\right\rfloor$. Therefore, if $i\leq t\leq 2i-1$, we know $f(i,t)=i$. Otherwise, we have $f(i,3i-1)=0$. Then, define the sequence $t_{i,1}=3i-1$ and $t_{i,j}=t_{i,j-1}+1+\left\lfloor\frac{t_{i,j-1}+1}{2}\right\rfloor$ for each positive integer $j\geq 1$. For convenience, define $t_{i,0}=2i-1$. When $j>0$, each $t_{i,j}$ satisfies $f(i,t_{i,j})=0$, so if $t_{i,j-1}<t\leq t_{i,j}$, then $f(i,t)=t_{i,j}-t$. Since $t_j\geq\frac{3}{2}t_{j-1}$ and $\left(\frac{3}{2}\right)^{110}>10^{18}$, we only need to compute at most $110$ values of the sequence to calculate the value of $f(i,t)$, which is fast enough for subtask 2.

Full solution:

For each $l_1\leq t\leq r_1$, there are two cases: $t\leq 2i-1$ and $t\geq 2i$.

If $t\leq 2i-1$, then $f(i,t)=i$. In the interval $l_1\leq i\leq r_1$, the values of $i$ which satisfy this inequality are $\max\left(l_1,\frac{t+1}{2}\right)\leq i\leq r_1$. Then, $l_2\leq f(i,t)\leq r_2$ corresponds to the inequality $l_2\leq i\leq r_2$. The values of $i$ that satisfy both inequalities are

If $t\geq 2i$, then $f(i,t)=t_{i,j}-t$ when $t_{i,j-1}<t\leq t_{i,j}$ and $1\leq j\leq 110$. Fix some $j$. The values of $i$ which satisfy $i\leq\frac{t}{2}$, $l_1\leq i\leq r_1$, $l_2\leq t_{i,j}-t\leq r_2$, $t\leq t_{i,j}$, and $t_{i,j-1}<t$ form an interval. The last three inequalities simplify to $l_2+t\leq t_{i,j}\leq r_2+t$ and $t_{i,j-1}\leq t-1$.

To compute the interval of $i$ that satisfies these inequalities, we will calculate the maximum value of $i$ such that $t_{i,j}\leq x$ for some fixed $j$ and $x$. Since $t_{i,j}$ is an increasing function for fixed $j$, the values of $i$ which satisfy $t_{i,j}\leq x$ are exactly $i\leq a$ for some integer $a$. The inequality is always true when $j=0$, so we can say that the maximum value of $i$ is a large number greater than $10^{18}$. When $j=1$, the inequality is $3i-1\leq x$, so the maximum $i$ is $\left\lfloor\frac{x+1}{3}\right\rfloor$. For $j\geq 2$, we use recursion to rewrite the inequality as $t_{i,j-1}+1+\left\lfloor\frac{t_{i,j-1}+1}{2}\right\rfloor\leq x$. The inequality is true if and only if $t_{i,j-1}\leq\left\lfloor\frac{2x-2}{3}\right\rfloor$. If we define the function $g(n)=\left\lfloor\frac{2n-2}{3}\right\rfloor$, then $t_{i,j}\leq x$ if and only if $t_{i,j-1}\leq g(x)$. Therefore, we can continue this process to get $t_{i,j}\leq x$ if and only if $t_{i,1}\leq g^{j-1}(x)$, which simplifies to $3i-1\leq g^{j-1}(x)$.

We can calculate the arrays $\mathrm{inv1}[j]=g^{j-1}(t-1)$, $\mathrm{inv2}[j]=g^{j-1}(l_2+t-1)$, and $\mathrm{inv3}[j]=g^{j-1}(r_2+t)$ for $1\leq j\leq 110$ quickly, and set $\mathrm{inv1}[0]=\mathrm{inv2}[0]=\mathrm{inv3}[0]>10^{18}$. The inequalities $l_2+t\leq t_{i,j}\leq r_2+t$ and $t_{i,j-1}\leq t-1$ is equivalent to the inequalities $3i-1\leq\mathrm{inv3}[j]$, $3i-1>\mathrm{inv2}[j]$, and $3i-1\leq\mathrm{inv1}[j-1]$. Therefore, the number of $i$ in the interval described by these three inequalities and the two inequalities $i\leq\frac{t}{2}$ and $l_1\leq i\leq r_1$ can be calculated in $\mathcal O(1)$ time for each $j$.

The total time complexity is $\mathcal O(110Q)$.

#include <bits/stdc++.h>
using namespace std;

vector<long long> inv(long long n){
    vector<long long> ans;
    ans.push_back(4000000000000000000);
    for(int i=0;i<111;i++){
        ans.push_back(n);
        n = (2*n+4)/3-2;
    }
    return ans;
}

int main(){
    int q;
    cin >> q;
    while(q--){
        long long l1,r1,l2,r2,t;
        cin >> l1 >> r1 >> l2 >> r2 >> t;

        long long ans = 0;
        vector<long long> inv1 = inv(t-1);
        vector<long long> inv2 = inv(l2+t-1);
        vector<long long> inv3 = inv(r2+t);
        for(int j=1;j<111;j++){
            // l1 <= i <= min(t/2,r1)
            // 3*i-1 <= min(inv1[j-1],inv3[j])
            // 3*i-1 > inv2[j]
            long long low = max(l1,(inv2[j]+4)/3);
            long long high = min(min(t/2,r1),(min(inv1[j-1],inv3[j])+4)/3-1);
            ans += max(0LL,high-low+1);
        }

        // l1 <= i <= r1
        // l2 <= i <= r2
        // t <= 2*i-1
        ans += max(0LL,min(r1,r2)-max(max(l1,l2),t/2+1)+1);
        cout << ans << endl;
    }
}