A - 0.001 USD
B - 0.001 USD
C1 - 0.002 USD
C2 - 0.003 USD
D - 0.005 USD
E - 0.01 USD
F1 - 0.03 USD
F2 - 0.05 USD
G - 0.1 USD
H1 - 0.1 USD
H2 - 0.1 USD

Let $$$f(n)$$$ denote the required value for $$$n$$$. Let $$$b$$$ be the index of the MSB of $$$n$$$. We’ll formulate $$$f(n)$$$ recursively.

Notice that we can split $$$f(n)$$$ into parts $$$A$$$ and $$$B$$$ — where $$$A$$$ is the concatenation of binary numbers $$$1, \ldots, (2^b - 1)$$$, and $$$B$$$ is that of numbers $$$2^b, \ldots, n$$$.

For example $$$f(6) = 11011100101110$$$. Here $$$b=2$$$, $$$A$$$ is $$$11011$$$ (corresponding to numbers 1, 2, and 3), and $$$B$$$ is $$$100101110$$$ (corresponding to numbers 4, 5, and 6).

Clearly, $$$A = f(2^b - 1)$$$.

We’ll now separate out the contribution of bits corresponding to $$$2^b$$$ to part $$$B$$$.

Rewriting, $$$B = 100100100 + 000001010$$$.

The first addend is the contribution of $$$2^b$$$, and it is just the sum of a GP $$$(10^3 + 10^6 + 10^9)$$$. We can calculate this quickly (under modulo) using binary exponentiation. Let’s call this contribution sum $$$c$$$.

The second addend is quite similar to the original problem — it is the concatenation of the binary representations of $$$(2^b - 2^b), (2^b + 1 - 2^b), \ldots, (n - 2^b)$$$. The (simplifying) change is that each binary number is padded with leading zeros to always have $$$(b + 1)$$$ digits.

Let’s define a new function $$$g(l, n)$$$ which denotes exactly this — concatenation of binary numbers $$$0, \ldots, n$$$, with each binary taking $$$l$$$ digits. We’ll figure out how to compute this recursively. This will solve the problem for us, since:

You can similarly break $$$g(l, n)$$$ into two parts, splitting where the MSB of $$$n$$$ appears. Both halves here are quite symmetric, since all binary lengths are equal. Do a similar calculation of the contribution of the MSB (call it $$$c'$$$), and you’ll get a clean recursive form for $$$g$$$ as well:

This is nice, but takes $$$O(n)$$$ calls to complete the recursion tree. To fix it, memoise and AC :D

(As an intuition for why memoisation works, notice that the left call always has the argument of the form $$$(2^k - 1)$$$, which means it can only have $$$\log(n)$$$ distinct values. The right call just strips off the bits of the initial $$$n$$$ one by one, going from the MSB to the LSB, which is again atmost $$$log(n)$$$ steps.)

Python code for reference.

Sort all points by their positions. We’ll try to simulate Kruskal’s algorithm. Notice that while running Kruskal’s on this graph, the connected components will all be contiguous ‘subarrays’ of these sorted points. (More formally, there exists a sorted order of edges such that adding them in order, […])

We’ll store all relevant edges in a priority queue $$$P$$$ and repeatedly pick the smallest. Initially, each point is a separate component. The relevant edges are only ones that join two adjacent components. If a component currently contains points $$$[l, r]$$$, then $$$P$$$ should contain (upto) two edges corresponding to extending this component: one merging it with $$$r + 1$$$, and another merging it with $$$l - 1$$$.

All that remains is to quickly calculate the cost of extending a component to one side. In other words, we need $$$\min \limits_{l \leq i \leq r} a[i] \cdot (p[i] - p[l - 1])$$$ (for one side). This can be done using CHT, maintaining two sets (one for each side) for each component in the UFDS along with small-to-large merging.

for(int i=2;i<n;i++){
  if(a[i-1]+a[i+1]==4){
    a[i]=min(a[i],4-a[i]);
  }
}
for(int i=n-1;i>=2;i--){
  if(a[i-1]+a[i+1]==4){
    a[i]=min(a[i],4-a[i]);
  }
}

ko4ary m4t4t

OK, Here is the English translation of the text:

Child, is your mindset aligned with the goals of studying informatics Olympiad (IO)?
The rules are designed to keep you from slacking off, but you keep focusing on how restrictive they feel. Think carefully for yourself and adjust your mindset. One measure we suggest is to create your own plan and stick to it, no matter what.

Through scientific adjustment, such as exercising, running, and implementing a self-made plan, you can improve. If your mindset collapses every few days, it’s likely to happen again during a major competition. Learning IO should be a joyful experience. If it feels like a burden, a constraint, or even suffering, why are you doing it?

You need to manage your emotions by creating a scientifically sound plan, learning how to learn, and expressing negative emotions through reading, walking outside, or exercising. If you repeatedly let yourself wallow, your emotions will accumulate and eventually explode, leading to extreme outcomes. IO is inherently challenging; it won’t become easier just because you’re anxious or impatient.

Child, is your mindset truly suitable for pursuing IO?
Rules exist to prevent you from slacking off, yet you dwell on how they constrain you. Reflect and adjust your attitude. One approach is to set a plan and push yourself to complete it. Through scientifically guided actions like exercise, running, and sticking to your plans, you’ll progress. If you lose your composure every few days, chances are you’ll lose it during major competitions as well. Learning IO should be a source of happiness—if it’s only a burden or source of frustration, why continue?

Child, from the time I’ve known you, I’ve noticed that you tend to see only one side of things.
Every issue has multiple facets. You need to learn to view situations from multiple perspectives. The rules we’ve set for assignments aim to prevent you from falling behind, wasting time, or mindlessly playing games. Look around—has anyone been punished for sincerely studying IO? Those who persist with a steady mindset don’t fall behind. Focus on studying patiently.

When you can’t solve a problem, ask for help and explanations. Studying IO is manageable—platforms like Codeforces (CF) and Atcoder offer excellent problems. Solving even two or three can make a difference. Approach it step by step, patiently tackling one concept at a time.

Originally, I intended to discuss these points during my duty hours with you.

To All Students:
There will be training during the Mid-Autumn Festival on Sunday and Monday from 8:00 AM to 9:00 PM. Junior high school students are encouraged to attend, and high school students may join. For high school students, the priority remains the upcoming monthly exam. If any student has travel plans, feel free to go—exploring the world is important too. On Tuesday (Mid-Autumn Day), let the students rest and enjoy the day. Let’s combine work and leisure.

Training during Mid-Autumn Festival (15th-16th):
The training sessions will be held in the computer lab on the third floor of Tsinghua Campus from 8:00 AM to 9:00 PM. Junior high students are advised to attend. High school students can join if their cultural studies and reviews are on track, but they need to bring their own notebooks.

Additionally, there is a CSP-S exam on the 21st, which conflicts with the high school sports day. Please plan your schedule. Participation in CSP is mandatory to qualify for NOIP. Plan your time wisely. For those with travel plans during Mid-Autumn, training is optional. Seeing the world is also important, as is participating in sports events. High school students, good luck with your monthly exams.

Regarding Unsolved Problems:
If you encounter problems you don’t understand, don’t force them, especially ones prone to errors. If you can’t write SPJ (Special Judge), don’t overcomplicate it.

Look around—has anyone been penalized for sincerely studying IO? We evaluate based on results and performance. Those who perform well will be identified through competitions and tasks.

If a student is not suitable for training in this group, decisions can be made openly and transparently, focusing on practical solutions. After CSP, those who don’t achieve high scores might reconsider their paths. For later competitions like NOIP, different levels and grades will have varying criteria. I believe democratic discussions and open communication can work well in this context.

On Decision-Making:
A lack of decisiveness is itself a problem. Whether you choose cultural studies or IO, commit fully. Don’t listen solely to teachers or parents—listen to your own inner voice. Once you’ve made a decision, stick to it, and don’t waver after a few days. If you underperform, accept it as your chosen path and move forward.

Competitions are high-pressure and require determination, decisiveness, and unwavering commitment. Hesitation leads to wasted time and energy. Learn to face challenges with clarity and problem-solving strategies.

Finally, remember that setbacks are inevitable, but how you approach them defines your progress. Reflect on these points and think critically about your decisions.

This translation captures the original's intent and nuances, emphasizing the themes of mindset, perseverance, scientific planning, and constructive self-reflection.

以下是还原后的中文句子：

孩子，你这种心态是不是和搞信奥的志趣不相符？制度是约束你们别退废的，你总去想制度对你的枷锁。你自己考虑好，自己要调整这种心态。咱们的一个措施是自己制定计划，并且自己咬着牙完成。

通过科学的调整，比如运动、跑步，自己制定计划并实施。你这三天两头心态就不行了，崩一次，大赛的时候也大概率会崩。学信奥是快乐的事，如果你现在学它是枷锁，是约束，是痛苦了，你还学它干什么？

这种情绪需要自己制定科学的计划，学会学习，通过看书、走出来，通过运动把负面情绪发泄出来。如果你一天两头这样，你的情绪积累到一定程度会爆发的，走向极端的。信奥就是这么难，它不会因为你着急或者不着急，就会变简单。

孩子，你这种心态是不是和搞信奥的志趣不符？制度是约束你们别退废的，你总去想制度对你的枷锁。你自己考虑好，自己要调整这种心态。咱们的一个措施是自己制定计划，并且自己咬着牙完成。通过科学的调整，比如运动、跑步，自己制定计划并实施。你这三天两头心态就不行了，崩一次，大赛的时候也大概率会崩。学信奥是快乐的事，如果你现在学它是枷锁，是约束，是痛苦了，你还学它干什么？

孩子，从接触你，发现你看事情容易就只看到事情的一面，事情是有多面的。你要学会看这个多面性。我们制定制度让你们做题，做题书的源头是怕你们堕落，怕你们偷偷地玩游戏，扯淡。你看谁因为天天做题书，我们罚，我们念咒？自己要心定，没堕落，你就耐心地学。做题书实际上也好办，同伴有完成的简单题，你还没完成，求助讲解就可以了。自己耐心研究那个知识点，耐心研究就是了。CF、Atcoder上那么多好题，做两道就是了，第七点，小台阶。

本来这些打算我值班的时候，和你谈谈的。

各位同学，中秋放假，周日、周一训练，早晨8:00-21:00，初中同学建议来，高中同学可以来。高中同学还是以第一次月考为主。如果有同学有出行计划，可以去，看世界很重要。周二中秋这天，让孩子们好好休息，好好玩玩。老一结合。

各位同学，中秋节15、16号早8:00-21:00，在清华小区3楼机房训练。初中同学建议都要参加，高中同学在文化课学习、复习没有问题的情况下，可以来训练，但要自带笔记本。另外21号有CSP-S的考试，和高中学校运动会冲突，大家规划好时间，参加，不参加CSP是参加不了NOIP的。大家把时间规划好，中秋有出行计划，不强制参加训练，看世界也很重要，参加运动会也很重要。祝高中同学，月考加油。

孩子，你们弄不明白的题，就不要考，特别容易引起问题。SPJ不会写就别弄。

你看谁正常学OI被我们罚了？我们现在只看结果，以成绩说话。你看谁成绩好我们罚了？因为，我们就可以通过联赛成绩，大家做题情况逐渐地去筛查。那你这个是去筛查谁？我为什么不太强调大家，但是说如果大家大大方方地说“老师，我觉得在这个团队里面，谁谁谁谁谁是在退废的。”那大家都这么想，那对这个同学也不是说我们非得要整他。大家大大方方地说你不适合在这个团队里训练，那就先把他们现在形式上都先停止在A层团队，试行可行的方案。因为咱们要快速地试行可行的方案，知道吧？但是说那你说要是永远陷入这种纷争就没有可行的方案。那或者大家就说，谁谁谁退了。

啊，就是，然后咱马上找地方处理，然后他要是承认，那咱们就大家大大方方地去干。都是面对面的，没有退后保证的。你别，咱们同学你知道吗，我跟大家也说了，背后大家说了些什么其实我都不太听。因为这世界都是人性，这不好。大家就大大方方地，我引导大家大大方方地说。那咱们就快速地去，把咱们这里面的人，先进行合理的分配。这是一个分配方式。第二个是CSP之后，没得一等奖的人，那他现在往前冲也没有啥意义了，有的倒一步减少。然后呢，后面NOIP呢，那个不同年级设置是不一样的限制。然后呢，我觉得我们后面啊，大家自由民主或者这种方式是能接受的。一个年级找出来一个我最想冲的人做代表，咱们几个教练去大大方方地跟我们谈论现在这个制度问题。但是这个事的所有核心就是每个人都要固定的，固定的。因为你跟这个同学说的时候他就会陷入到“老师，他怎么怎么样，他怎么怎么样。”那你说是不是也会陷入到这种纷争中？

由于自己没有主见本身就是问题。学信奥，你没有主见就会你在做决策选择的时候就犹豫不决啊。你要越过这种思维障碍，内心想怎么干就怎么干。你选文化课，你就努力考，也要能考上。你决定争信奥，你就争。别听老师的，也不要听你爸的。听你自己内心的声音，你自己内心的声音。你归着选择了，你归着等弄完。我们决定的那后面你又觉得又不一样了，你又会犹豫。你这些都是错误的。我就觉得不是，特别正确的思维。你自己仔细想想这个事儿吧，又犹豫不决。

选竞赛呢，就更加坚定，它是一条比文化课要更加极致的路。因为你既要兼顾文化课，又要弄几个才。晚上睡觉的时候，你问问自己内心的声音。你决定了，就一条道走到底，别过几天就变卦了，那是你自己，就是考得不好，你转身自己走，那是你自己走的路。小伙儿，我也不建议你问你爸的意见，就是你自己决定了，就怎么干。因为假如说这个事儿，因为竞赛就是高压力，它需要坚定，需要果断，需要坚定的选择。如果你内心不是这样想的，那你你后面往后拖，那后面你还会犹豫这个事儿。就这样，你想想分析分析老师说这个事儿是不是这样？

那你看你这个犹豫呀，过程这个过程特别慢，这个过程，你大包的内心想着这个过程是很长是不是内耗？事实没有意义。那这个事情已经发生了，咱们就接受这个事情发生。那我们下下一次给它考好不就完了吗？这才是正确的思维，解决问题的思维。那你陷入寻思寻思，寻思你没练没练那么多，那你打那些分儿不正常吗？

这段文字主要围绕学生的心态调整、信奥学习以及训练、竞赛的规划展开，内容较长且复杂，整体强调调整心态、坚定目标、科学规划的重要性，同时提及相关活动安排与管理。

#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
#define int long long

int n, m, k, p, q, u, v, w, l, r, x, y, z;
using ll = long long;
using ull = unsigned long long;
const int N = 2e5 + 10, inf = 1e9;
int mod = 1e9 + 7;
const ll linf = 1e18;

mt19937_64 randll(chrono::steady_clock::now().time_since_epoch().count());

struct Line {
    mutable ll k, m, p; // k -> slope :: m -> intercept
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct hull : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = inf, 0;
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

vector<hull> lhul(N), rhul(N);
vector<int> cl(N), cr(N), cc(N);
set<vector<int>> st; // cst, c1, c2

int find(int i) {
    return i == cc[i]? i : cc[i] = find(cc[i]);
}

int res;

void merge(hull &a, hull &b) {
    if (a.size() < b.size()) {
        swap(a, b);
    }
    for (Line l : b) {
        a.add(l.k, l.m);
    }
}
vector<pair<int, int>> vec;

void merge(int a, int b, int c) {
    a = find(a), b = find(b);
    if (a == b) return;
    res += c;
    if (a > b) swap(a, b);
    cc[b] = a;
    merge(rhul[a], rhul[b]);
    merge(lhul[a], lhul[b]);
    cl[a] = min(cl[a], cl[b]);  
    cr[a] = max(cr[a], cr[b]);
    if (cl[a]) {
        vector<int> v = {-lhul[a].query(vec[cl[a] - 1].first), a, find(cl[a] - 1)};
        st.insert(v);
    } if (cr[a] + 1 < n) {
        vector<int> v = {-rhul[a].query(vec[cr[a] + 1].first), a, find(cr[a] + 1)};
        st.insert(v);
    }
}

void solve (int tc = 1) {
    cin >> n;
    st.clear();
    for (int i = 0; i < n; i++) {
        lhul[i].clear();
        rhul[i].clear();
        cl[i] = cr[i] = cc[i] = i;
    }
    vec.resize(n);
    for (int i = 0; i < n; i++) cin >> vec[i].first;
    for (int i = 0; i < n; i++) cin >> vec[i].second;
    sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i++) {
        auto [x, y] = vec[i];
        rhul[i].add(-y, x * y);
        lhul[i].add(y, -x * y);
        if (i + 1 < n) {
            vector<int> v = {-rhul[i].query(vec[i + 1].first), i, i + 1};
            st.insert(v);
        }
        if (i) {
            vector<int> v = {-lhul[i].query(vec[i - 1].first), i, i - 1};
            st.insert(v);
        }
    }
    res = 0;
    while (!st.empty()) {
        vector<int> v = *st.begin();
        st.erase(v);
        merge(v[1], v[2], v[0]);
    }
    for (int i = 0; i < n; i++) assert(find(i) == find(0));
    cout << res;
}
    
#undef int

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int tc = 1;
    cin >> tc;
    // scanf("%d", &tc);
    while (tc--) {
        solve(tc);
        if (tc) cout << nl;
        // if (tc) printf("\n");
    }
}

But i was happy with my delta ;)

Use deques