Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
946 B
1
Indexable
#include<bits/stdc++.h>
using namespace std;
int sum(int i,int j,int *prf)
{
    if (i==0)
        return prf[j];
    return prf[j]-prf[i-1];
}
void solve()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for (auto &x:v)cin>>x;
    int prf[n];
    prf[0]=v[0];
    for (int i=1;i<n;++i)prf[i]=prf[i-1]+v[i];
    set<int>s;
    int output=0;
    for (int i=1;i<n;++i)
    {
        if(v[i]<=v[i-1])
        {
            output++;
            s.insert(i-1);
        }
        else
        {
            while(!s.empty())
            {
                int r=*(--s.end());
                s.erase(r);
                if (sum(r,i-1,prf)>=v[i])
                {
                    output+=(i-r);
                    s.insert(r);
                    break;
                }
            }
        }
    }
    cout<<output;
}
signed  main() {
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    int t=1;
    while(t--)solve();
}

Leave a Comment