Codeforces Round #935 Разбор

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

1945A - Разбиваем лагерь

Разбор

Решение

#include <iostream>

using namespace std;
using ll = long long;

void solve() {
    ll single, poly, uni;
    cin >> single >> poly >> uni;
    ll needPoly = (3 - poly % 3) % 3;
    if (poly > 0 && needPoly > uni) {
        cout << "-1\n";
        return;
    }

    uni -= needPoly;
    poly += needPoly;

    ll mn = single + uni / 3 + (uni % 3 + 1) / 2 + poly / 3;
    cout << mn << '\n';
}

int32_t main() {
    ll T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

1945B - Фейерверки

Идея: NToneE, Gadget

Разбор

Решение

t = int(input())
for qi in range(t):
    a, b, m = [int(x) for x in  input().split()]
    ans = m // a + m // b + 2
    print(ans)

1945C - Левые и правые дома

Идея: Gadget, NToneE

Разбор

Решение

for case in range(int(input())):
    n = int(input())
    a = input()
    suf_cnt = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suf_cnt[i] = suf_cnt[i + 1] + (a[i] == '1')
    pref_cnt = 0
     
    opt_ans = -1
    opt_dist = n * 2
    threshold = (n + 1) // 2
     
    for i in range(n + 1):
        if pref_cnt >= (i + 1) // 2 and suf_cnt[i] >= (n - i + 1) // 2 and abs(n - 2 * i) < opt_dist:
            opt_dist = abs(n - 2 * i)
            opt_ans = i
        if i != n:
            pref_cnt += (a[i] == '0')
     
    print(opt_ans)

1945D - Филин Серафим

Идея: Kirill_Maglysh

Разбор

Решение

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> A(n);
    for (auto& item : A) {
        cin >> item;
    }
    reverse(A.begin(), A.end());

    vector<ll> B(n);
    for (auto& item : B) {
        cin >> item;
    }
    reverse(B.begin(), B.end());

    ll bSum = 0;
    ll pref = 0;
    for (ll i = 0; i < n - k; ++i) {
        if (A[i] < B[i]) {
            pref += bSum;
            pref += A[i];
            bSum = 0;
        } else {
            bSum += B[i];
        }
    }

    ll res = 1e18;
    for (ll i = n - k; i < n; ++i) {
        res = min(res, pref + bSum + A[i]);
        bSum += B[i];
    }

    cout << res << '\n';
}

int32_t main() {
    ll testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

1945E - Бинарный поиск

Идея: Kirill_Maglysh

Разбор

Решение

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> src(n);
    int P = 0;
    for (int i = 0; i < n; ++i) {
        cin >> src[i];
        if (src[i] == x) {
            P = i;
        }
    }

    int l = 0;
    int r = n;
    while (r - l > 1) {
        int m = (l + r) / 2;

        if (src[m] <= x) {
            l = m;
        } else {
            r = m;
        }
    }

    cout << "1\n";
    cout << P + 1 << ' ' << l + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

1945F - Кирилл и грибы

Идея: Kirill_Maglysh

Разбор

Решение

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
using ll = long long;

void solve() {
    ll n;
    cin >> n;
    vector<ll> src(n);
    vector<pair<ll, ll>> can(n);
    for (ll i = 0; i < n; ++i) {
        cin >> src[i];
        can[i] = {src[i], i};
    }

    vector<ll> ord(n);
    for (auto& item : ord) {
        cin >> item;
        --item;
    }

    sort(can.rbegin(), can.rend());
    ll best = can[0].first;
    ll take = 1;

    ll cur;
    ll P = 1;
    vector<bool> burn(n);
    vector<bool> used(n);
    used[can[0].second] = true;
    for (ll k = 0; k + 1 < n && P < n; ++k) {
        while (P < n && burn[can[P].second]) {
            ++P;
        }

        if (P == n) {
            break;
        }

        used[can[P].second] = true;
        cur = can[P].first;
        ++P;

        burn[ord[k]] = true;
        if (used[ord[k]]) {
            while (P < n && burn[can[P].second]) {
                ++P;
            }

            if (P == n) {
                break;
            }

            used[can[P].second] = true;
            cur = can[P].first;
            ++P;
        }

        if (best < cur * (k + 2)) {
            take = k + 2;
            best = cur * (k + 2);
        }
    }

    cout << best << ' ' << take << '\n';
}

int32_t main() {
    ll testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

1945G - Повар и каша

Идея: Kirill_Maglysh

Разбор

Решение

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using ll = long long;

const int MAX_N = 2e5;
const int MAX_D = 3e5;

struct Student {
    int k;
    int s;
    int tin = 0;

    bool operator<(const Student& other) const {
        if (k == other.k) {
            if (tin == other.tin) {
                return s > other.s;
            }
            return tin > other.tin;
        }
        return k < other.k;
    }
};

int n, D, x;
Student qu1[MAX_N];
int sufMax[MAX_N];
vector<Student> eat[MAX_D];

int check() {
    int origPos = 0;
    priority_queue<Student> qu2;
    for (int i = 0; i < D && origPos < n; ++i) {
        if (qu2.empty() || qu2.top().k <= sufMax[origPos]) {
            ll nxtTime = ll(i) + ll(x) * ll(qu1[origPos].s);
            if (nxtTime < D) {
                eat[nxtTime].push_back(qu1[origPos]);
            }

            ++origPos;
            if (origPos == n) {
                for (int tm = 0; tm < D; ++tm) {
                    eat[tm].clear();
                }

                return i + 1;
            }
        } else {
            ll nxtTime = ll(i) + ll(x) * ll(qu2.top().s);
            if (nxtTime < D) {
                eat[nxtTime].push_back(qu2.top());
            }
            qu2.pop();
        }

        for (const auto& student : eat[i]) {
            qu2.push({student.k, student.s, i});
        }
    }

    for (int i = 0; i < D; ++i) {
        eat[i].clear();
    }

    return -1;
}

void solve() {
    cin >> n >> D;
    x = 1;
    for (int i = 0; i < n; ++i) {
        cin >> qu1[i].k >> qu1[i].s;
    }

    sufMax[n - 1] = qu1[n - 1].k;
    for (int i = n - 2; i >= 0; --i) {
        sufMax[i] = max(qu1[i].k, sufMax[i + 1]);
    }

    cout << check() << '\n';
}

int32_t main() {
    ll testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

1945H - НОД больше

Идея: Kirill_Maglysh

Разбор

Решение

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int BITS = 20;
const int MAX_N = 4e5 + 10;
int n;
int x;

int src[MAX_N];

void coutYES(int fId, int sId) {
    cout << "YES\n";
    cout << "2 " << src[fId] << ' ' << src[sId] << '\n';
    cout << n - 2 << ' ';
    for (int i = 0; i < n; i++) {
        if (i == fId || i == sId) {
            continue;
        }
        cout << src[i] << ' ';
    }
    cout << '\n';
}

void solve() {
    cin >> n >> x;
    vector<int> bitCnt[BITS];

    int maxA = 1;
    for (int i = 0; i < n; i++) {
        cin >> src[i];
        maxA = max(maxA, src[i] + 1);
        for (int bit = 0; bit < BITS; bit++) {
            if ((1 << bit) & src[i]) {
                continue;
            }

            bitCnt[bit].push_back(i);
        }
    }

    bool incr[n];
    int cnt[maxA];
    int divBy[maxA];
    for (int i = 0; i < maxA; ++i) {
        cnt[i] = 0;
        divBy[i] = 0;
    }

    int pref[n];
    int suf[n];
    for (int i = 0; i < n; i++) {
        incr[i] = false;
        pref[i] = src[i];
        if (i) {
            pref[i] = pref[i - 1] & src[i];
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        suf[n - 1] = src[n - 1];
        if (i < n - 1) {
            suf[i] = suf[i + 1] & src[i];
        }
    }

    for (const auto& item : bitCnt) {
        if (item.size() <= 2) {
            for (const int& id : item) {
                incr[id] = true;
                int myAnd = -1;
                for (int j = id + 1; j < n; j++) {
                    int curAND = (1 << BITS) - 1;
                    if (j + 1 < n) curAND &= suf[j + 1];
                    if (id - 1 >= 0) curAND &= pref[id - 1];
                    if (myAnd != -1) curAND &= myAnd;

                    if (curAND + x < __gcd(src[id], src[j])) {
                        coutYES(id, j);
                        return;
                    }

                    if (myAnd == -1) {
                        myAnd = src[j];
                    } else {
                        myAnd &= src[j];
                    }
                }

                myAnd = -1;
                for (int j = id - 1; j >= 0; j--) {
                    int curAND = (1 << BITS) - 1;

                    if (j - 1 >= 0) curAND &= pref[j - 1];
                    if (id + 1 < n) curAND &= suf[id + 1];
                    if (myAnd != -1) curAND &= myAnd;

                    if (curAND + x < __gcd(src[id], src[j])) {
                        coutYES(id, j);
                        return;
                    }

                    if (myAnd == -1) {
                        myAnd = src[j];
                    } else {
                        myAnd &= src[j];
                    }
                }
            }
        }
    }

    int AND = (1 << BITS) - 1;
    for (int i = 0; i < BITS; i++) {
        if (!bitCnt[i].empty()) {
            AND ^= (1 << i);
        }
    }

    for (int i = 0; i < n; i++) {
        if (!incr[i]) {
            ++cnt[src[i]];
        }
    }

    for (int i = 1; i < maxA; i++) {
        for (int j = i; j < maxA; j += i) {
            divBy[i] += cnt[j];
        }
    }

    for (int g = maxA - 1; g > AND + x; g--) {
        if (divBy[g] < 2) {
            continue;
        }

        int fId = -1;
        int sId = -1;
        for (int i = 0; i < n; i++) {
            if (!incr[i]) {
                if (src[i] % g == 0) {
                    if (fId == -1) {
                        fId = i;
                    } else {
                        sId = i;
                    }
                }
            }
        }
        coutYES(fId, sId);
        return;
    }

    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int testN;
    cin >> testN;
    while (testN--) {
        solve();
    }
    return 0;
}

vector<int> a(n); vector<int> b(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; } if(m==n){ cout << a[n-1] << endl; return; } long long ans = 0; long long c = 0; for (int i = n-1; i >=m; i--) { ans+=min(a[i],b[i]); } long long ans1=1e18; for (int i = m-1; i >=0; i--) { ans1 = min(ans+a[i]+c,ans1); c+=b[i]; } cout << ans1 << endl;

vl a(n), b(n); for (auto& it : a) { cin >> it; } for (auto& it : b) { cin >> it; } ll sum = 0; ll ans = 1e18; for (int i = n - 1; i >= 0; --i) { sum += min(a[i], b[i]); if (i < m) { ans = min(ans, sum - min(a[i], b[i]) + a[i]); } } cout << ans << '\n';

vector<int> right(n+1); right[n] = 0; for(int i=n-1; i>=0; i--){ right[i] = (s[i] == '1') + right[i + 1]; } int mini = 0, diff = n; int cnt = 0; for(int i=0; i<n; i++){ cnt = cnt + (s[i] == '1'); int left0 = i + 1 - cnt; int right1 = right[i+1]; int atlL = (i + 1) / 2 + (i + 1) % 2; int atlR = (n - i - 1) / 2 + (n - i - 1) % 2; if((left0 >= atlL) && (right1 >= atlR) && abs(n - 2*(i + 1)) < diff){ mini = i + 1; diff = abs(n - 2*(i + 1)); } } cout << mini << endl;

// this is code #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i=a; i<=b; i++) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<string, string> pss; typedef vector<int> vi;typedef vector<vi> vvi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<vl> vvl; double EPS = 1e-9;int INF = 1000000005; long long INFF = 1000000000000000005ll; double PI = acos(-1); int dirx[8] = { -1, 0, 0, 1, -1, -1, 1, 1 }; int diry[8] = { 0, 1, -1, 0, -1, 1, -1, 1 }; int main() { ios::sync_with_stdio(false); cin.tie(0); ll t;cin>>t; while(t--){ ll n,m;cin>>n>>m; vl a(n+1,0);for(int i=1;i<=n;i++)cin>>a[i]; vl b(n+1,0);for(int i=1;i<=n;i++)cin>>b[i]; ll sum=0; // ll i=n; while(n>m){ sum+=min(a[n],b[n]); n--; } if(m==1){ sum+=a[m]; } else{ sum+=min(b[m]+a[m-1],a[m]); } // sum+=min() cout<<sum<<endl; } } }

Комментарии (47)

Написать комментарий?

theRealChainman

9 месяцев назад, # |

+11

For problem G the editorial has the swapped inequality it should be suffixMax_p >= k(Q2_front), because that indicates there is a larger k in the suffix of Q1 that highest priority person in Q2 would be waiting behind.

→ Ответить

lightmon

E was subtle

TalkySafe143

For problem D we can consider a dp approach: let $$$dp_i$$$ the minimum ammount of coins for reach the position $$$i$$$, thus:

$$$ dp_i= \begin{cases} a_n & \text{if } i = n \\ \min\{a_i+dp_{i+1}, a_i+dp_{i+1}-a_{i+1}+b_{i+1}\} & \text{otherwise} \end{cases}$$$

We can calculate solutions from $$$dp_1$$$ and choose $$$\min\limits_{1 \le i \le m}{dp_i}$$$. The basic idea is to choose between pay $$$b_i$$$ or $$$a_i$$$ for all $$$i$$$.

exulansis

9 месяцев назад, # ^ |

can you explain the first sample test case of D. the answer should be swap with place 2 and pay 3+8 = 11. how is it 14?

← Rev. 2 →

If we swap with the 2nd position, you also must pay $$$b_n = 5$$$ because initially you will stand in $$$n+1$$$ place and this give you $$$16$$$. I'll simulate the solution for the first test case

Consider $$$dp_4 = 9$$$, so we move on to $$$dp_3$$$, we must choose:

$$$dp_3 = \min\{a_i+dp_{i+1}, a_i+dp_{i+1}-a_{i+1}+b_{i+1}\}$$$ $$$dp_3 = \min\{6+dp_{4}, 6+dp_{4}-9+5\}$$$ $$$dp_3 = \min\{15, 11\}$$$

$ So, $$$dp_3 = 11$$$. The second part of the $$$\min$$$ function represent that we consider took $$$b_{i+1}$$$ instead of $$$a_{i+1}$$$, in this case $$$dp_3$$$ choose $$$b_4$$$ because if we want to reach $$$i=3$$$, it will be optimal to choose $$$a_3+b_4$$$. At this moment we have $$$dp_3=11$$$, so we will calculate $$$dp_2$$$ as follows: $$$dp_2 = \min(3+11, 3+11-6+8) = \min(14, 16)$$$ so $$$dp_2 = 14$$$ and actually this is the minimum value for $$$dp_i, 1 \le i \le 2$$$. This solution says that is optimal to choose $$$a_2+a_3+b_4$$$.

AJ7787_

3 месяца назад, # ^ |

CAN you please explain how did this expression for the dp come? what i mean is that what is the logic behind this expression

bruce_x001

Problem E Video Editorial Audio : (Hindi)

YOUTUBE VIDEO LINK ---Click Here

codetoalive

There's actually quite an elegant implementation for problem F:

https://codeforces.net/contest/1945/submission/252463604

mouradnouaili

Please guys, l'd like to know why I het a WA? Problem F: https://codeforces.net/contest/1945/submission/252370876

Thanks.

Fuad

At problem B,

"At the moment x, there will be fireworks in the sky, released at moments [x, x+a, …, x+a⋅⌊m/a⌋]"

Please explain.

yariss

8 месяцев назад, # ^ |

Let's consider the first launch station.

When the station has its first launch, you can construct the following interval $$$I=[a, a+m]$$$, where $$$I$$$ represents all the moments in which a firework $$$x$$$ is visible.

Let's say $$$a=6$$$ and $$$m=4$$$, then $$$I=[6,10]$$$. If we want to count the maximum number of fireworks in this interval, it's clearly $$$\lfloor\frac{10}{6}\rfloor=1$$$, which is when $$$x=6$$$ (the next $$$x$$$ is $$$12\notin I$$$).

Now you do the same for the second launch station $$$b=7$$$, and the answer becomes $$$\lfloor\frac{10}{6}\rfloor + \lfloor\frac{11}{7}\rfloor= 2$$$.

Formally, $$$ans=\lfloor\frac{a+m}{a}\rfloor + \lfloor\frac{b+m}{b}\rfloor$$$ , which is $$$2 + \lfloor\frac{m}{a}\rfloor + \lfloor\frac{m}{b}\rfloor$$$

somanyducks

Problem F can be simulated with an ordered statistic tree :p

252626826

carolinux

7 месяцев назад, # ^ |

Indeed: https://codeforces.net/contest/1945/submission/263511065

__AhmedSamir__

Solving B using binary search - The key to solve this problem lies in the concept of binary search on the answer. We aim to find the largest integer value x such that x * a — a <= m.

We start by initializing a binary search range with st = 0 and en set to a sufficiently large value, say 10^20 (we can't in c++ so use python). Then, we perform a binary search within this range. At each step, we calculate the midpoint mid and check if mid * a — a <= m. If this condition holds true, it means we can increase our search range. Thus, we update st = mid. Otherwise, we need to decrease our search range, so we update en = mid — 1. We repeat this process until we find the maximum valid value for x. This process has a time complexity of O(log n).
We apply the same binary search approach to determine the maximum number of fireworks launched at intervals of b, 2b, 3b, and so forth.
Finally, we sum the maximum values obtained from both binary searches to obtain the total maximum number of fireworks launched within the given time frame m. This sum represents our answer. https://codeforces.net/contest/1945/submission/252638271

hjacobs3

You definitely overcomplicated this. Simply find LCM of a and b to find the first time when fireworks are launched at the same time. Then, simply calculate how many fireworks would be launched between common start time and m.

Very simple: https://codeforces.net/contest/1945/submission/254889075

md_nihal

← Rev. 4 →

In C sample 1.

3
101
outut:2

"can't we insert at 0 the villagers to right side 2 of 3 are satisfied ?

If there are multiple suitable positions i with the minimum ∣n2−i∣, output the smaller one."

bhanu2306

+14

In that problem n/2 is not rounded to an integer, it may be a decimal value

Thanks solved

noobcoder8055

Well For the Problem E only one swap is sufficient in every case ? my solution got accepted but don't know how....? can anyone explain

_NonSense_

nvm, i got it lol good contest btw

Mamun064

For C,why n/2, it's a real number didn't mention in the problem statement?

__Anvith__

Can someone please help me in finding my mistake for submssion 252896905 to problem F?

darkkcyan

I think the problem G's statement is still not 100% clear. If 2 students with the same priority, finishing their dishes at the same time, who will go to the queue first?

I tried to solve this solve this by assuming the one who goes out eating first will come back first, but apparently this seems to not be the case. The comparator function in the solution prioritize the student with higher eating time first. This seems very unnatural to me.

Though the problem idea didn't change much if a more strictly description was added. This is still a cool problem. Though this bug me for hours, not know where I was wrong.

tw107y

Question does say

"If several schoolchildren return at the same time, they will return to the queue in ascending order of their si."

a-a-a

Can anyone explain E? Not able to get it from the tutorial.

ahmetalp

We know this binary search gives a number which is always <=X. (If you are not sure about that, you can try some examples.)

Assume P is position of X.

If we change this result and P, we can find X. Because only once we asked to P. And smaller number will give same answer(make l = mid). So we will get same index before don't swapped P and result.

Got it, Thanks

arghya_G

https://codeforces.net/contest/1945/submission/253021750

why this solution is giving runtime error on testcase 2 in problem D

Axial-Tilted

H's tutorial is no unclear i'd love if somebody explains what the tutorial wants us to do i only understand why its always beneficial to take 2 numbers as the red and that the AND cant be less than the AND of the entire array , i dont get the rest ( the middle paragraph ) such as

we if a cet certain bit y is equal to zero in more than two numbers

Why more than 2 numbers ? if we have the bit x 0 in a certain number then it'll be 0 in the AND unless we take that number as red ?? so many questions

in problem H why if a bit is 0 in more than 2 numbers then its 0 in the AND ? i understand that if we have 3 or more numbers with bit x 0 in them then it'll always be zero in the finally AND but sometimes we can have only 1 number with bit x equal to 0 and still the finally AND will have that bit 0 if we dont consider it in the red numbers ? the middle paragraph is unclear hope somebody rewrites it in a more clear way , thanks

adaptatron

Your understanding is correct. Suppose we are dealing with $$$x^{th}$$$ bit. There are 3 cases:

None of the numbers contain a 0 at this position : The AND would contain 1.
There are $$$> 2$$$ 0 at this position. The AND would contain 0.
There are 1 or 2 zero at this position. Then, we are not sure about the AND. But, let's pick one element with zero at this position, move it to the blue set, and then, let's try to pair it up with all possible elements. If no match could be found, then we know for sure that the element belongs to the red set, hence making the AND zero.

I've added more details here

Yea thanks I got it , it wasn't clear at the beginning I feel like it would've been more clear if they stated why we try all numbers where the bit is 0 in no more than 2 but now that I get it I feel like it's self explanatory

shashankvashistha1

Understanding problem statement C is 80% and solving it is 20%. Problem statement of [problem:C] is really confusing.

ankit02

for D question is tough to understand

vinty

Someone please explain what this line means in tutorial for problem H: "We will iterate through each of these numbers as one of the red numbers, and iterate through the second one for n " , where are we iterating for second number and how? Need some explanation .

krishnakumar

Folks, wanted to validate an alternate brute complex idea for problem E.

The binary search tree of ranges would consist of 2n-1 nodes at max, with depth of log2n.

Each leaf node is the node where the search ends, we can try to find the total number of swaps required for the number to be at this node, were the binary search to happen from root to this leaf node.

Any leaf node that requires <= 2 swaps would be an answer.

varrick

Problem D editorial contains typo, $$$b_k$$$<$$$a_k$$$ should be there.

wbw121124

$$$\Huge \text{hello!!!}$$$

bachkhairi

8 месяцев назад, # |

Problem D

before reaching the position m why not simply take the minimum of a[i] and b[i] ?? and then consider the sum of pref and bSum ??

something like this

int n,m; cin >> n >> m;

BitTheDebugger

i did same during practice for D void solve() { ll n, m; cin >> n >> m;

}

oxygen_06_05

Problem B: Please explain this line: At the moment x, there will be fireworks in the sky, released at moments [x, x+a, …, x+a⋅⌊m/a⌋[user:Gadget].

Pulkit95700

7 месяцев назад, # |

Hey anyone can you tell me about what is the wrong with the constraints for the problem C here. I would like to know what is the error in my code here. I can't figure it out

void solve() { ll n; cin >> n; string s; cin >> s;

Your code here...

Sekai02

Problem F. Kirill and Mushrooms can actually be solved using Fenwick Tree:

Let us fix the number of mushrooms for a potion. Let this number be $$$k \leq n$$$. Now we have to maximize the minimum value that we choose for this potion. This number is the $$$k-th$$$ maximum, lets call this number $$$mxmin$$$. And we update the answer with $$$ans=min(ans,mxmin*k)$$$.

Fenwick Tree allow us to find the $$$k-th$$$ maximum, wich is equivalent to findind the $$$(rem - k + 1)-minimum$$$ with BinaryLifting. Where $$$rem$$$ is the remaining number of mushrooms. You can find how to do this in this blog

When we go from $$$k$$$ mushrooms to $$$k+1$$$ mushrooms we have to update the FenwickTree by subracting the value of the $$$p[k]$$$ mushroom.

See the code for any other detail: My submission

AksLolCoding

For problem F you can just use order statistic tree and use find_by_order to solve in nlogn time.

neol_lies

4 месяца назад, # |

I think there is an error in editorial of problem D

Spoiler

maddy30445r

what test case does this miss for D problem cant we just smaller between a[i] and b[i] as we can anyways stop at any index.

Блог пользователя Kirill_Maglysh