#include "candies.h"

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

const int MX=2e5+5;

typedef long long ll;

struct node {
        ll sum, res[2], pref[2], suff[2];

        node() {
                sum=0;
                res[0]=1e18;
                res[1]=-1e18;

                pref[0]=1e18;
                pref[1]=-1e18;

                suff[0]=1e18;
                suff[1]=-1e18;
        }
};

node merge(node a, node b) {
        node c;
        c.sum=a.sum+b.sum;
        c.res[0]=min(a.res[0],b.res[0]);
        c.res[1]=max(a.res[1],b.res[1]);

        c.pref[0]=min(a.pref[0],a.sum+b.pref[0]);
        c.suff[0]=min(b.suff[0],b.sum+a.suff[0]);
        c.pref[1]=max(a.pref[1],a.sum+b.pref[1]);
        c.suff[1]=max(b.suff[1],b.sum+a.suff[1]);

        c.res[0]=min(c.res[0],c.pref[0]);
        c.res[0]=min(c.res[0],c.suff[0]);
        c.res[1]=max(c.res[1],c.pref[1]);
        c.res[1]=max(c.res[1],c.suff[1]);

        return c;
}

struct segtree {
        node t[4*MX];

        void upd(int v, int l, int r, int pos, int x) {
                if(pos<l||r<pos) return;
                if(l==r) {
                        node c;
                        c.sum=x;
                        c.res[0]=c.res[1]=x;
                        c.pref[0]=c.pref[1]=x;
                        c.suff[0]=c.suff[1]=x;
                        t[v]=c;
                        return;
                }
                int m=(l+r)/2;
                upd(v*2,l,m,pos,x);
                upd(v*2+1,m+1,r,pos,x);
                t[v]=merge(t[v*2],t[v*2+1]);
        }

        node que(int v, int l, int r, int ql, int qr) {
                if(qr<l || r<ql) return node();
                if(ql<=l && qr>=r) return t[v];
                int m=(l+r)/2;
                return merge(que(v*2,l,m,ql,qr),que(v*2+1,m+1,r,ql,qr));
        }
} st;

int N,Q;
vector<int> ans;
vector<pair<int,int>> line[MX];

std::vector<int> distribute_candies(std::vector<int> C, std::vector<int> L,
                                    std::vector<int> R, std::vector<int> V) {   

        N=C.size();
        Q=L.size();
        ans.resize(N);

        for(int i=0;i<Q;i++) {
                line[L[i]].push_back({V[i],i});
                line[R[i]+1].push_back({0,i});
        }

        for(int i=0;i<N;i++) {
                for(auto [v,j]:line[i]) {
                        st.upd(1,0,Q-1,j,v);
                }

                int l=0,r=Q-1,x=-1,y=-1;
                while(l<=r) {
                        int m=(l+r)/2;
                        if(st.que(1,0,Q-1,m,Q-1).res[0]<=-C[i]) {
                                x=m,l=m+1;
                        } else {
                                r=m-1;
                        }
                }
                l=0,r=Q-1;
                while(l<=r) {
                        int m=(l+r)/2;
                        if(st.que(1,0,Q-1,m,Q-1).res[1]>=C[i]) {
                                y=m,l=m+1;
                        } else {
                                r=m-1;
                        }
                }

                if(x==-1 && y==-1) {
                        ans[i]=st.que(1,0,Q-1,0,Q-1).sum;
                        continue;
                }

                if(x<y) {
                        int l=y,r=Q-1,p=-1;
                        while(l<=r) {
                                int m=(l+r)/2;
                                if(st.que(1,0,Q-1,y,m).res[1]>=C[i]) {
                                        p=m,r=m-1; 
                                } else{
                                        l=m+1;
                                }
                        }
                        ll s=st.que(1,0,Q-1,p+1,Q-1).sum;
                        ans[i]=C[i]+min(0ll,s);
                } else {
                        int l=x,r=Q-1,p=-1;
                        while(l<=r) {
                                int m=(l+r)/2;
                                if(st.que(1,0,Q-1,x,m).res[0]<=-C[i]) {
                                        p=m,r=m-1; 
                                } else{
                                        l=m+1;
                                }
                        }
                        ll s=st.que(1,0,Q-1,p+1,Q-1).sum;
                        ans[i]=max(0ll,s);
                }
        }

        return ans;
}