HackerEarth Xsquare And Maximum Sum Subarray solution

In this HackerEarth Xsquare And Maximum Sum Subarray problem Xsquare has decided to win next Programming Marathon and started his preparation for the same. Xsquare's coach advised him to revise algorithmic concepts and to try twik of some standard problem. Xsquare's coach knows that it is the only best strategy to perform well at any kind of marathon.

Xsquare started following his coach's instructions and getting better and better as the day passes. One fine day, Xsquare has taken up the following standard problem.

Given a one dimensional array A of size N that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum.

Xsquare modified the above problem to make it bit more interesting .

Given a one dimensional array A of size N that may contain both positive and negative integers and an integer K, find the sum of contiguous subarray of numbers which has the largest sum such that no element in the selected array is greater than K. To make this problem a bit harder, Xsquare decided to add Q queries to this problem each containing one integer i.e K.

HackerEarth Xsquare And Maximum Sum Subarray problem solution.

#include <bits/stdc++.h>
using namespace std ;
#define LL long long int
#define ft first
#define sd second
#define PII pair<int,int>
#define MAXN 1000001
#define mp make_pair
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
#define pb push_back
#define MOD 1000000007
#define inf 11111111111LL

class node{
    public :
    LL left_best_sum , right_best_sum , best_sum ,total_sum ;
    bool setbit ;
    node(){
        left_best_sum  = -inf ;
        right_best_sum = -inf ;
        best_sum  = -inf ;
        total_sum = 0 ;
        setbit = 1 ;
    }
};


class SegTree{

    public :
    vector<node> st ;
    vector<int> A ;
    int N ;

    SegTree(int N,vector<int> &A){
        this->N = N ;
        (this->A).resize(N+1) ;
        st.resize(4*N+1) ;
        for(int i=1;i<=N;i++){
            (this->A)[i] = A[i] ;
        }
    }

    void _merge(node &a,node &b,node &c){
        a.best_sum = max(b.right_best_sum+c.left_best_sum,max(b.best_sum,c.best_sum)) ;
        if(b.setbit){
            a.left_best_sum = b.left_best_sum ;
        }else{
            a.left_best_sum = max(b.left_best_sum,b.total_sum+c.left_best_sum) ;
        }
        if(c.setbit){
            a.right_best_sum = c.right_best_sum ;
        }else{
            a.right_best_sum = max(c.right_best_sum,c.total_sum+b.right_best_sum) ;
        }
        a.total_sum = b.total_sum + c.total_sum ;
        a.setbit = (b.setbit|c.setbit) ;
    }

    void buildst(int idx,int ss,int se){
        if(ss == se){
            st[idx].best_sum = A[ss] ;
            st[idx].left_best_sum = A[ss] ;
            st[idx].right_best_sum = A[ss] ;
            st[idx].total_sum = A[ss] ;
            st[idx].setbit = 0 ;
            return ;
        }
        int mid = (ss+se)/2 ;
        buildst(2*idx,ss,mid) ;
        buildst(2*idx+1,mid+1,se) ;
        _merge(st[idx],st[2*idx],st[2*idx+1]) ;
    }

    void update(int idx,int ss,int se,int pos,int val=1){
        if(ss == se){
            st[idx].setbit = 1 ;
            st[idx].best_sum = -inf ;
            st[idx].left_best_sum = -inf ;
            st[idx].right_best_sum = -inf ;
            st[idx].total_sum = 0 ;
            return ;
        }
        int mid = (ss+se)/2 ;
        if(pos <= mid)
            update(2*idx,ss,mid,pos,val) ;
        else
            update(2*idx+1,mid+1,se,pos,val) ;
        _merge(st[idx],st[2*idx],st[2*idx+1]) ;
    }

    node query(int idx,int ss,int se,int L,int R){
        node ret ;
        if(L > se || R < ss){
            return ret ;
        }
        if(L <= ss && se <= R){
            return st[idx] ;
        }
        int mid = (ss+se)/2 ;
        node left  = query(2*idx,ss,mid,L,R) ;
        node right = query(2*idx+1,mid+1,se,L,R) ;
        _merge(ret,left,right) ;
        return ret ;
    }
} ;

int T,N,Q,K;
vector<int> A ;
vector<LL> ans;
vector<PII> B,queries ;
int main(){
   // f_in("in00.txt") ;
  // f_out("out00.txt") ;
    sc(N) ;sc(Q) ;
    A.resize(N+1) ;
    B.resize(N+1) ;
    ans.resize(Q+1) ;
    queries.resize(Q+1) ;
    for(int i=1;i<=N;i++){
        sc(A[i]) ;
        B[i].ft = A[i] ;
        B[i].sd = i ;
    }
    for(int i=1;i<=Q;i++){
        sc(queries[i].ft) ;
        queries[i].sd = i ;
    }
    sort(B.begin()+1,B.end()) ;
    sort(queries.begin()+1,queries.end()) ;
    SegTree *obj = new SegTree(N,A) ;
    obj->buildst(1,1,N) ;
    int i,j ;
    i = Q ;
    j = N ;
    while( i > 0 ){
        int x = queries[i].ft ;
        while(j > 0 && B[j].ft > x){
            obj->update(1,1,N,B[j].sd) ;
            j -- ;
        }
        ans[queries[i].sd] = (obj->query(1,1,N,1,N).best_sum) ;
        i -- ;
    }

    for(int i=1;i<=Q;i++){
        if( ans[i] == -inf ){
            printf("No Solution\n") ;
        }else{
            pr(ans[i]) ;
        }
    }
    return 0 ;
}

Second solution

#include <bits/stdc++.h>
#define lli long long
#define MAX 500005
#define INF 10000000000000000LL
using namespace std;

pair <lli, lli> Q[MAX];
pair <lli, lli> A[MAX];
lli ans[MAX];

struct node {
    lli ans;
    lli pre;
    lli suf;
    lli sum;
    node() { }
    node(lli ans, lli pre, lli suf, lli sum)
    {
        this->ans = ans;
        this->pre = pre;
        this->suf = suf;
        this->sum = sum;
    }
}tree[4*MAX];

node combine(node p1, node p2)
{
    node ret;
    ret.sum = max(-INF, p1.sum + p2.sum);
    ret.pre = max(-INF, max(p1.pre, p1.sum + p2.pre));
    ret.suf = max(-INF, max(p2.suf, p1.suf + p2.sum));
    ret.ans = max(p1.ans,p2.ans);
    ret.ans = max(-INF, max(ret.ans, p1.suf + p2.pre));
    return ret;
}

void build(int where, int left, int right)
{
    if ( left > right ) return;
    if ( left == right ) {
        tree[where] = node(-INF,-INF,-INF, -INF);
        return;
    }
    int mid = (left+right)/2;
    build(where*2, left, mid);
    build(where*2+1, mid+1, right);
    tree[where] = combine(tree[where*2], tree[where*2+1]);
}

void update(int where, int left, int right, int idx, lli val)
{
    if ( left > right || left > idx || right < idx ) return;
    if ( left == right ) {
        tree[where] = node(val, val, val, val);
        return;
    }
    int mid = (left+right)/2;
    update(where*2, left, mid, idx, val);
    update(where*2+1, mid+1, right, idx, val);
    tree[where] = combine(tree[where*2], tree[where*2+1]);
}

template <typename T>
inline void fi(T *a)
{
    register char c=0;
    while (c<33) c=getchar_unlocked();
    *a=0;
    int tmp = 0;
    while (c>33)
    {
        if ( c == 45 ) tmp = 1;
        else *a=*a*10+c-'0';
        c=getchar_unlocked();
    }
    if ( tmp == 1 ) *a = 0-(*a);
}

int main()
{
    int n,q,idx1,idx2;
    fi(&n), fi(&q);
    build(1,0,n-1);
    for ( int i = 0; i < n; i++ ) {
        fi(&A[i].first);
        A[i].second = i;
    }

    sort(A,A+n);

    for ( int i = 0; i < q; i++ ) {
        fi(&Q[i].first);
        Q[i].second = i;
    }

    sort(Q, Q+q);

    idx1 = idx2 = 0;

    while ( idx1 < q ) {
        while ( idx2 < n && A[idx2].first <= Q[idx1].first ) {
            update(1,0,n-1,A[idx2].second,A[idx2].first);
            idx2++;
        }
        ans[Q[idx1].second] = tree[1].ans;
        idx1++;
    }
    for ( int i = 0; i < q; i++ ) {
        if ( ans[i] == -INF ) printf("No Solution\n");
        else printf("%lld\n", ans[i]);
    }
    return 0;
}