Clutch or kick#12200

Clutch or kick (Shpjegimi i zgjidhjes)

Problem Author:	Kostiantyn Denysov
Prepared by:	Maksym Shvedchenko and Iliia Shevchenko
Editorial by:	Maksym Shvedchenko

Let's apply the divide and conquer idea. Suppose we are given a segment $[L, R]$ , and let its midpoint be $M$ . We will now consider all subsegments that lie inside $[L, R]$ and pass through $M$ .

To handle this, we build all suffix sums on the left side and all prefix sums on the right side. Then we sort them and use a two-pointer technique: for a given suffix we maintain the maximum prefix such that their sum does not exceed $s$ , and similarly, for a given prefix we maintain the maximum suffix.

After that, we sort everything back and simply traverse prefix and suffix maxima in order to update the answer for each element inside the segment. This gives us a solution in $O (n lo g^{2} n)$ O(n \log^2 n).

However, if we recall that mergesort is also essentially a divide-and-conquer algorithm, we can sort these prefixes and suffixes together in total $O (n lo g n)$ O(n \log n) time using mergesort.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <unordered_map>
#include <queue>
#include <random>
#include <stack>

using namespace std;
#define int long long
int mod = 1000000007;
int log_ = 22;
int inf = 30000000000000000;
int n, s;
vector <int> a;
vector <pair <int, int>> pref;
vector <pair <int, int>> syf;
vector <int> p;
vector <int> ans;
vector <pair <int, int>> rem;

int rec(int l, int r) {
    if (l == r) {
        if (a[l] <= s)
            ans[l] = a[l];
        return a[l];
    }
    int m = (l + r) / 2;
    int s1 = rec(l, m);
    int s2 = rec(m + 1, r);
    int S = 0;
    int I = m + 1;
    for (int i = l; i <= r; i++)
        p[i] = -inf;

    for (int i = m; i >= l; i--) {
        while ((I <= r) and (pref[I].first <= s - syf[i].first)) {
            S = pref[I].first;
            I++;
        }

 

        if (S + syf[i].first <= s) {
            p[syf[i].second] = S + syf[i].first;
        }
        else
        {
            p[syf[i].second] = -inf;

        }
    }

    int x = -inf;
    for (int i = l; i <= m; i++) {
        x = max(x, p[i]);
        ans[i] = max(ans[i], x);
    }
    S = 0;
    I = l;

    for (int i = r; i >= m+1; i--) {
        while ((I <= m) and (syf[I].first <= s - pref[i].first)) {
            S = syf[I].first;
            I++;
        }

        if (S + pref[i].first <= s) {
            p[pref[i].second] = S + pref[i].first;
        }
        else
        {
            p[pref[i].second] = -inf;
        }
    }
    x = -inf;
    for (int i = r; i > m; i--) {
        x = max(x, p[i]);
        ans[i] = max(ans[i], x);
    }

    for (int i = l; i <= m; i++) {

        syf[i].first += s2;

    }

    for (int i = m+1; i <= r; i++) {

        pref[i].first += s1;

    }

    int i1 = l;
    int i2 = m + 1;

    for (int i = l; i <= r; i++) {
        if (i1 == m + 1) {
            rem[i] = pref[i2];
            i2++;
            continue;
        }
        if (i2 == r + 1) {
            rem[i] = pref[i1];
            i1++;
            continue;
        }

 
        if (pref[i1] < pref[i2]) {
            rem[i] = pref[i1];
            i1++;
            continue;
        }
        else {
            rem[i] = pref[i2];
            i2++;
            continue;
        }
    }
    for (int i = l; i <= r; i++) {
        pref[i] = rem[i];
    }
    i1 = l;
    i2 = m + 1;
    for (int i = l; i <= r; i++) {
        if (i1 == m + 1) {
            rem[i] = syf[i2];
            i2++;
            continue;
        }
        if (i2 == r + 1) {
            rem[i] = syf[i1];
            i1++;
            continue;
        }

        if (syf[i1] < syf[i2]) {
            rem[i] = syf[i1];
            i1++;
            continue;
        }
        else {
            rem[i] = syf[i2];
            i2++;
            continue;
        }
    }


    for (int i = l; i <= r; i++) {
        syf[i] = rem[i];
    }
    return s1 + s2;

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int times;
    cin >> times;
    while (times--)
    {
        cin >> n >> s;
        a.resize(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        pref.resize(n);
        syf.resize(n);
        rem.resize(n);
        ans.clear();
        p.resize(n);
        ans.resize(n, -inf);
        for (int i = 0; i < n; i++) {
            pref[i] = { a[i] , i };
            syf[i] = { a[i] , i };
        }
        rec(0, n - 1);
        for (int i = 0; i < n; i++) {
            if (ans[i] == -inf)
                cout << 'x' << " ";
            else
                cout << ans[i] << " ";
        }
        cout << "\n";
    }
}