# Tutorial for D - Yet Another Real Number Problem

## Problem overview

[Link to problem](https://codeforces.com/contest/2035/problem/D)

**Tags:** ==binary search, bitmasks, data structures, dp, greedy, implementationmath, two pointers.==

I suppose that you've read and understand the problem statement, now we head to the editorial.

## Solution

My idea is to maintain the list of number that can be divided by $2$ and contribute to the current number.

More formally, if we iterate up to position $i$, we will have a **priority_queue** with a **pair<int, int>**, for any number $x = 2^y \times v$, it is stored as $[v, y]$. For example, if the number is $20 = 2^2 \times 5$, then it is stored as $[5, 2]$, if the number is $120 = 2^3 \times 3 \times 5$, then it is stored as $[15, 3]$.

The top value in the **priority_queue** is the smallest ones (as we construct this greedily).

Suppose that we reach a pair of value $[x, cnt]$ in **pq** and currently iterate up to position $i$ . How can we check whether we should perform all operations for this pair to contribute for $a[i]$ ?

We also break $a[i]$ down as mentioned earlier (i.e $a[i] = 2^p \times y$), then we can compare the value before and after performing all operations :

- Before : $y \times 2^p + x \times 2^{cnt}$
- After : $y \times 2^{p + cnt} + x$

The total sum can increase only if the after value is $\geq$ than the berfore value, that is :
$$
\begin{align}
y \times 2^{p + cnt} + x &\geq y \times 2^p + x \times 2^{cnt} \\
\Leftrightarrow\text{ } y \times 2^{p + cnt} - y \times 2^p &\geq x \times 2^{cnt} - x \\
\Leftrightarrow\text{ } y \times 2^p \times 2^{cnt} - y \times 2^p &\geq x \times 2^{cnt} - x \\
\Leftrightarrow\text{ } y \times 2^p \times (2^{cnt} - 1) &\geq x \times (2^{cnt} - 1) \\
\Leftrightarrow\text{ } y \times 2^p &\geq x
\end{align}
$$

We've just broken it down to a very easy comparable expression, now this is how i compare it :
- If $p > 31$, then $y \times 2^p \geq x$ is always true.
- If $p <= 31$, then it fits at least into **long long** data type in **C++**, we just compare it normally.

After knowing that we can perform all operations, we just do it :)

## Implementation

Until now, you can implement it by yourself or read this :

All the variable names i've declared above are compatible with ones in the source code :)

:::spoiler Source code with detailed instructions

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

/*
  John Watson
  Handle codeforces : quangminh98

  Mua Code nhu mua Florentino !!
*/

#define ll long long

string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while (t--) solve();

    return 0;
}

// main program
const int mod = 1e9 + 7;

int add(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
int mul(int a, int b) { return (1ll * a * b) % mod; }

int power(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b % 2 == 1)
            res = mul(res, a);
        a = mul(a, a);
        b /= 2;
    }
    return res;
}

void solve()
{
    int n; cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];

    int cur = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 1; i <= n; i++)
    {
        // update current value
        cur = add(cur, a[i]);
        
        // get the form of a[i] as described earlier
        int p = 0;
        while (a[i] % 2 == 0)
        {
            p++;
            a[i] /= 2;
        }
        int y = a[i];
        
        while (!pq.empty())
        {
            int x = pq.top().first, cnt = pq.top().second;

            // whether we can perform all operations for this
            bool great= false;
            // compare as analysed earlier
            if (p > 31)
                great = true;
            else
                if (1ll * (1 << p) * y >= x) // remember to add 1ll
                    great = true;
            if (!great) break;

            pq.pop();

            // now we can proceed, we substract the old values while adding new ones
            cur = sub(cur, mul(power(2, p), a[i]));
            cur = add(cur, mul(power(2, p + cnt), a[i]));
            cur = sub(cur, mul(x, power(2, cnt)));
            cur = add(cur, x);
            // also remember to update the power
            p += cnt;
        }

        // if p is equal to 0, it means the value cannot be divided by 2
        // we only push value that can be used 
        if (p != 0)
            pq.push({y, p});

        cout << cur << ' ';
    }
    cout << '\n';
}

:::
<br>

**Time complexity :** $O(t \times n \times log_2(n)$

My <span style="color: green;">**Accepted**</span> source code : [Link](https://codeforces.com/contest/2035/submission/288402884)

Having any questions ? DM me in codeforces : [Link](https://codeforces.com/profile/quangminh98)