FracoesBinarias.cpp

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 10;

int v[MAXN], dp[MAXN];
int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);

    int n; cin >> n;

    for(int i = 1; i <= n; i++)
    {
        int a,b; cin >> a >> b;

        //v[i] guarda a i-ésima fração na forma de uma única potência
        v[i] = log2(a) - log2(b);
    }

    int resp = 0;
    for(int i = 1; i <= n; i++)
    {
        //dp é a seg de kadane. Se tiver alguma dúvida, acesse a aula de soma máxima em intervalo
        dp[i] = max(dp[i - 1] + v[i], v[i]);
        resp = max(resp, dp[i]);
    }

    // out será o output
    // inicializamos ele em 1 porque se resp for negativo é mais vantajoso só pegar um intervalo vazio
    int out = 1;

    //para quando resp = 0 ou quando resp > 0, já que um int = 0 pode ser interpretado com um bool "false"
    while(resp-- && resp > 0)
    {
        //multiplico out por 2 resp vezes, já que resp é o expoente do intervalo que queremos
        out *= 2;
        //tiro mod, para adequar a resposta ao que é pedido no problema.
        out %= MOD;
    }
    cout << out;
}