Code : Slimes

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

long long get_sum(vector<long long> &pref, int l, int r) {
    return pref[r] - (l ? pref[l - 1] : 0);
}

vector<int> solve(vector<int> &a) {
    int n = a.size();

    vector<long long> pref(n);
    pref[0] = a[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }

    vector<int> kill(n, inf), lst(n);
    lst[0] = 0;
    // kill[i] is the minimum time needed for the i-th cell to be killed by
    // its prefix. If it's not possible, it is set to infinity.
    for (int i = 1; i < n; i++) {
        lst[i] = i;
        if (a[i] == a[i - 1]) {
            lst[i] = lst[i - 1];
        }

        if (a[i - 1] > a[i]) {
            kill[i] = 1;
            continue;
        }

        int l = 0, r = i - 1, res = inf;
        while (l <= r) {
            int mid = (l + r) / 2;
            auto sum = get_sum(pref, mid, i - 1);

            if (sum <= a[i] || lst[i - 1] <= mid) {
                r = mid - 1;
            } else {
                res = i - mid;
                l = mid + 1;
            }
        }
        kill[i] = res;
    }

    return kill;
}

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

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        auto lkill = solve(a);
        reverse(a.begin(), a.end());
        auto rkill = solve(a);
        for (int i = 0; i < n; i++) {
            int now = min(lkill[i], rkill[n - 1 - i]);
            if (now < n) {
                cout << now << " ";
            } else {
                cout << -1 << " ";
            }
        }
        cout << "\n";
    }
}

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

const int inf = 1e9;

int rmnq_op(int a, int b) { return min(a, b); }

int rmnq_e() { return (int)(1e9) + 1; }

int rmxq_op(int a, int b) { return max(a, b); }

int rmxq_e() { return -1; }

long long get_sum(vector<long long> &pref, int l, int r) {
    return pref[r] - (l ? pref[l - 1] : 0);
}

vector<int> solve(vector<int> &a) {
    int n = a.size();
    segtree<int, rmnq_op, rmnq_e> rmnq(a);
    segtree<int, rmxq_op, rmxq_e> rmxq(a);

    vector<long long> pref(n);
    pref[0] = a[0];
    for (int i = 1; i < n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }

    vector<int> kill(n, inf);
    // kill[i] is the minimum time needed for the i-th cell to be killed by
    // its prefix. If it's not possible, it is set to infinity.
    for (int i = 1; i < n; i++) {
        if (a[i - 1] > a[i]) {
            kill[i] = 1;
            continue;
        }

        int l = 0, r = i - 1, res = inf;
        while (l <= r) {
            int mid = (l + r) / 2;
            auto sum = get_sum(pref, mid, i - 1);

            if (sum <= a[i] || rmnq.prod(mid, i) == rmxq.prod(mid, i)) {
                r = mid - 1;
            } else {
                res = i - mid;
                l = mid + 1;
            }
        }
        kill[i] = res;
    }

    return kill;
}

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

    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        auto lkill = solve(a);
        reverse(a.begin(), a.end());
        auto rkill = solve(a);
        for (int i = 0; i < n; i++) {
            int now = min(lkill[i], rkill[n - 1 - i]);
            if (now < n) {
                cout << now << " ";
            } else {
                cout << -1 << " ";
            }
        }
        cout << "\n";
    }
}