10 months ago

sumeet kumar sahoo • 290

Bengaluru

// one more problem

// approach:

iterate over the array mantaining a stack, if u encounter a -ve value push the index into the stack, when u encounter a +ve number check if the abs value of the top of the stack is smaller than the +ve element, if true set ans[stk.top()]=distance btw the elements, and subtract the -ve value from the +ve value and check again, and if abs value of the top of the stack is greater than the +ve element add +ve value the -ve value of the top of the stack and continue with iteration.

// code

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

int main() {
    
    int n;cin >> n;
    vector<int> v(n); for(int i=0;i<n;i++) cin >> v[i];

    stack<int> stk;
    vector<int> ans(n,0);
    for(int i=0;i<n;i++) {
        if(v[i]>=0) {
            ans[i]=1;
            while (stk.size() && abs(v[stk.top()])<=v[i]) {
                int curr=stk.top();
                ans[curr]=i-curr+1;
                stk.pop();
                v[i]+=v[curr];
            }
            if(stk.size()) v[stk.top()]+=v[i];
        }
        else stk.push(i);
    }

    for(int i=0;i<n;i++) cout << ans[i] << " ";
    cout << "\n";

    return 0;
}