Submission

[PPPPPPPP][PPPPPPPP][PPPPPPPPP]

Score: 100

User: 998244353

Problemset: 06.Happiness

Language: cpp

Time: 0.106 second

Submitted On: 2025-03-31 14:23:40

/*******************
* what  the  sigma *
********************/
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(x) tree<x, null_type, less<x>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define ve vector
#define ll long long
#define ld long double
bool enabledb=0;
#define DB(CODE) cout<<'\t'<<CODE<<endl;
#define SP <<' '<<
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int, int>
#define tii tuple<int,int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define pb push_back
const ll mod = 1e9+7,maxn=200005;
const ll INF=(ll)9e18;
ll seg[maxn*4],laz[maxn*4];
int a[maxn];
void build(int u,int l,int r) {
    if (l==r) {
        seg[u]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    seg[u]=min(seg[u<<1],seg[u<<1|1]);
}
void push(int u,int l,int r) {
    if (l<r) {
        seg[u<<1]+=laz[u];
        seg[u<<1|1]+=laz[u];
        laz[u<<1]+=laz[u];
        laz[u<<1|1]+=laz[u];
    }
    laz[u]=0;
}
void upd(int u,int l,int r,int tl,int tr,int v) {
    if (l>tr||r<tl) return;
    if (l>=tl&&r<=tr) {
        seg[u]+=v;
        laz[u]+=v;
        return;
    }
    push(u,l,r);
    int mid=(l+r)>>1;
    upd(u<<1,l,mid,tl,tr,v);
    upd(u<<1|1,mid+1,r,tl,tr,v);
    seg[u]=min(seg[u<<1],seg[u<<1|1]);
}
ll query(int u,int l,int r,int tl,int tr) {
    if (l>tr||r<tl) return 1e9;
    if (l>=tl&&r<=tr) {
        return seg[u];
    }
    push(u,l,r);
    int mid=(l+r)>>1;
    return min(query(u<<1,l,mid,tl,tr),query(u<<1|1,mid+1,r,tl,tr));
}
signed main() {
    lgm;
    int n;
    cin >> n;
    ve<pii> d;
    int c=0;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        if (a[i]>=0) {
            upd(1,1,n,i,n,a[i]);
            c++;
        } else {
            d.pb({a[i],i});
        }
    }
    sort(be(d),greater<pii>());
    for (auto [v,i]:d) {
        if (query(1,1,n,i,n)>=-v) upd(1,1,n,i,n,v),c++;
    }
    cout << c;
}