1788E - Sum Over Zero - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pll pair<ll,ll>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define oset ordered_set
#define rep(i,j,k) for(ll i=j;i<k;i++)
// #define endl "\n"
template <typename T> ostream& operator<<(ostream& os, vector<T>& v) {
    if(v.size() == 0) { os << "empty vector\n"; return os; }
    for(auto element : v) os << element << " ";
    return os;  }
template <typename T, typename S> ostream& operator<<(ostream& os, pair<T, S>& p) {
    os << "(" << p.first << ", " << p.second << ")"; return os;  }
template <typename T> ostream& operator<<(ostream& os, set<T>& v) {
    if(v.size() == 0) {  os << "empty set\n"; return os; }
    auto endit = v.end();  endit--;  os << "[";
    for(auto it = v.begin(); it != v.end(); it++) { os << *it; if(it != endit) os << ", "; }
    os << "]"; return os;  }
template <typename T> ostream& operator<<(ostream& os, multiset<T>& v) {
    if(v.size() == 0) { os << "empty multiset\n"; return os; }
    auto endit = v.end(); endit--; os << "[";
    for(auto it = v.begin(); it != v.end(); it++) {
      os << *it; if(it != endit)  os << ", "; }
      os << "]"; return os;  }
template <typename T, typename S> ostream& operator<<(ostream& os, map<T, S>& v) {
    if(v.size() == 0) { os << "empty map\n"; return os; }
    auto endit = v.end(); endit--; os << "{";
    for(auto it = v.begin(); it != v.end(); it++) {
        os << "(" << (*it).first << " : " << (*it).second << ")";
        if(it != endit)  os << ", "; } os << "}"; return os; }
template <typename T> ostream& operator<<(ostream& os, vector<vector<T>>& v) {
    for(auto& subv : v) { for(auto& e : subv) os << e << " "; os << "\n"; } return os; }

bool do_debug = false;

#ifndef ONLINE_JUDGE
#define de(var) cout << (#var) << ": " << var << endl
#else
#define de(var)
#endif
vector<ll> v,ps;
vector<ll> allv;
struct Segment_Tree
{
    ll N;
    vector<ll> seg_tree;
    ll merge(ll tl, ll tr, ll node1, ll node2)
    {
        return min(node1, node2);
    }
    void build_inner_same(ll node, ll tl,ll tr,ll val)
    {
        if(tl==tr) 
        {
            seg_tree[node] = val;
            return;
        }
        ll tm = (tl+tr)/2;
        build_inner_same(2*node, tl, tm,val);
        build_inner_same(2*node+1,tm+1, tr, val);
        seg_tree[node] = merge(tl,tr,seg_tree[2*node], seg_tree[2*node+1]);
    }
    void build_inner(ll node, ll tl,ll tr , vector<ll> &v)
    {
        if(tl==tr) 
        {
            seg_tree[node] = v[tl];
            return;
        }
        ll tm = (tl+tr)/2;
        build_inner(2*node, tl, tm,v);
        build_inner(2*node+1,tm+1, tr, v);
        seg_tree[node] = merge(tl,tr,seg_tree[2*node], seg_tree[2*node+1]);
    }
    Segment_Tree()
    {
        // Empty Constructor
    }
    Segment_Tree(vector<ll> &v)
    {
        N = v.size()-1;
        seg_tree.resize(4*N);
        build_inner(1,1,N,v);
    }
    Segment_Tree(ll siz, ll val)
    {
        N = siz;
        seg_tree.resize(4*N);
        build_inner_same(1,1,N,val);
    }
    ll query(ll l, ll r)
    {
        return query_inner(1,1,N,l,r);
    }
    void update(ll pos, ll val)
    {
        update_inner(1,1,N,pos,val);
    }
private:
   ll query_inner(ll node, ll tl, ll tr, ll l, ll r)
    {
        if(r<tl || l>tr) return 1e9;
        if(l<=tl  && r>=tr) return seg_tree[node];
        ll tm = (tl+tr)/2;
        ll num1 = query_inner(2*node, tl, tm, l, r);
        ll num2 = query_inner(2*node+1, tm+1, tr,l,r);
        return  merge(tl,tr,num1,num2);
    }
    void update_inner(ll node, ll tl, ll tr,ll pos, ll val)
    {
        if(tl==tr)
        {
            seg_tree[node] = min(seg_tree[node], val); return;
        }
        ll tm = (tl+tr)/2;
        if(pos<=tm) update_inner(2*node, tl, tm, pos, val);
        else update_inner(2*node+1,tm+1,tr,pos,val);
        seg_tree[node] = merge(tl,tr,seg_tree[2*node], seg_tree[2*node+1]);
    }
};
ll get_index(ll val)
{
    assert(binary_search(all(allv), val));
    return lower_bound(all(allv), val) - allv.begin()+1;
}
Segment_Tree st(2e5+1e4 , 1e9);
ll dp[200010];
ll solve(ll index)
{
    if(index<=0) return 0;
    if(dp[index]!=-1) return dp[index];
    ll ans1 = solve(index-1);
    ll small = st.query(1, get_index(ps[index]));
    if(small>=index) return dp[index]= ans1;
    ll ans2 = solve(small) + index-small;
    return dp[index] = max(ans1, ans2);

}
void Runtime_Terror()
{
   ll n;
   cin>>n;
   memset(dp, -1, sizeof(dp));
//    vector<ll> v(n+1);
    v.resize(n+1);
    ps.resize(n+1);
    rep(i,1,n+1) cin>>v[i];
   rep(i,1,n+1)
   {
     ps[i] = ps[i-1] + v[i];
   }
   rep(i,0,n+1) allv.push_back(ps[i]);
   allv.push_back(0);
   sort(all(allv));
   st.update(get_index(0), 0);
    vector<ll> dp(n+1);
    rep(i,1,n+1)
    {
        dp[i] = dp[i-1];
        ll num = st.query(1, get_index(ps[i]));
        de(i);
        de(num);
        dp[i] = max(dp[i], i - num);
        st.update(get_index(ps[i]), -dp[i] + i);
    }
    cout<<dp[n]<<endl;
    de(dp);
// cout<<"AC"<<endl;
       
       
       
}
int main()
{
   //freopen("input.txt", "r", stdin);
   //freopen("ans.txt", "w", stdout);
   ios_base::sync_with_stdio(false); cin.tie(NULL);
   int t=1;
    //  cin>>t;
   rep(i,0,t) Runtime_Terror();
   return 0;
}