Doubt in SPOJ GSS1

GSS1 Question
Why my code gives TLE? Should I still need to optimize my code or any infinite loops.Any Help would be appreciated… Link: Link to my code @tmwilliamlin @anudeep2011 @raunaqroxx

1 Like

Hi @mahatejvarma, I just changed vector v in main function to array and it worked

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node {
    ll sum,presum,sufsum,maxsum;
};
vector<node>segtree(1000002);
void build(ll *v,ll low, ll high, ll pos){
    if(low>high)return;
    if(low==high){
        segtree[pos].sum=v[low];
        segtree[pos].presum=v[low];
        segtree[pos].sufsum=v[low];
        segtree[pos].maxsum=v[low];
        return;
    }
    ll mid= (low+high)/2;
    build(v,low,mid,2*pos+1);
    build(v,mid+1,high,2*pos+2);
    segtree[pos].sum=segtree[2*pos+1].sum+segtree[2*pos+2].sum;
    segtree[pos].presum=max(segtree[2*pos+1].presum, segtree[2*pos+1].sum+segtree[2*pos+2].presum);
    segtree[pos].sufsum=max(segtree[2*pos+2].sufsum,segtree[2*pos+2].sum+segtree[2*pos+1].sufsum);
    segtree[pos].maxsum=max(segtree[pos].sufsum,
                        max(segtree[pos].presum,
                        max(segtree[2*pos+1].sufsum+segtree[2*pos+2].presum,
                        max(segtree[2*pos+1].maxsum,segtree[2*pos+2].maxsum))));


}
node query(ll ql , ll qh, ll low , ll high, ll pos){
    node result;
    result.sum=result.presum=result.sufsum=result.maxsum=INT_MIN;
    if(ql>high || qh<low || low>high)return result;
    if(low>=ql && high<=qh)return segtree[pos];

    ll mid=(low+high)/2;

    if (ql > mid) 
        return query(ql,qh,mid+1,high,2*pos+2);  
    if (qh <= mid) 
        return query(ql,qh,low,mid,2*pos+1); 

    node left=query(ql,qh,low,mid,2*pos+1);

    node right=query(ql,qh,mid+1,high,2*pos+2);

    result.sum=left.sum+right.sum;

    result.presum=max(left.presum, left.sum+right.presum);
    result.sufsum=max(right.sufsum,right.sum+left.sufsum);
    result.maxsum=max(result.sufsum,
                        max(result.presum,
                        max(left.sufsum+right.presum,
                        max(left.maxsum,right.maxsum))));
    return result;

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,q,j;
    cin>>n;
    //vector<ll>v(n);
    ll *v = new ll[n];
    
    for(i=0;i<n;i++)cin>>v[i];
    build(v,0,n-1,0);
    cin>>q;
    for(ll k1=0;k1<q;k1++){
        ll ql,qh;
        cin>>ql>>qh;
        node result=query(ql-1,qh-1,0,n-1,0);
       cout<< result.maxsum;
       if(k1!=q-1)cout<<"\n";
    }

}
1 Like

Thank you so much for taking a while bro…But why doesn’t it work with vector??

It can work with vector too if you passed it by reference. The following code works with the use of vector. I just passed the vector by reference. Check line 8

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node {
    ll sum,presum,sufsum,maxsum;
};
vector<node>segtree(1000002);
void build(vector<ll> &v,ll low, ll high, ll pos){
    if(low>high)return;
    if(low==high){
        segtree[pos].sum=v[low];
        segtree[pos].presum=v[low];
        segtree[pos].sufsum=v[low];
        segtree[pos].maxsum=v[low];
        return;
    }
    ll mid= (low+high)/2;
    build(v,low,mid,2*pos+1);
    build(v,mid+1,high,2*pos+2);
    segtree[pos].sum=segtree[2*pos+1].sum+segtree[2*pos+2].sum;
    segtree[pos].presum=max(segtree[2*pos+1].presum, segtree[2*pos+1].sum+segtree[2*pos+2].presum);
    segtree[pos].sufsum=max(segtree[2*pos+2].sufsum,segtree[2*pos+2].sum+segtree[2*pos+1].sufsum);
    segtree[pos].maxsum=max(segtree[pos].sufsum,
                        max(segtree[pos].presum,
                        max(segtree[2*pos+1].sufsum+segtree[2*pos+2].presum,
                        max(segtree[2*pos+1].maxsum,segtree[2*pos+2].maxsum))));


}
node query(ll ql , ll qh, ll low , ll high, ll pos){
    node result;
    result.sum=result.presum=result.sufsum=result.maxsum=INT_MIN;
    if(ql>high || qh<low || low>high)return result;
    if(low>=ql && high<=qh)return segtree[pos];

    ll mid=(low+high)/2;

    if (ql > mid) 
        return query(ql,qh,mid+1,high,2*pos+2);  
    if (qh <= mid) 
        return query(ql,qh,low,mid,2*pos+1); 

    node left=query(ql,qh,low,mid,2*pos+1);

    node right=query(ql,qh,mid+1,high,2*pos+2);

    result.sum=left.sum+right.sum;

    result.presum=max(left.presum, left.sum+right.presum);
    result.sufsum=max(right.sufsum,right.sum+left.sufsum);
    result.maxsum=max(result.sufsum,
                        max(result.presum,
                        max(left.sufsum+right.presum,
                        max(left.maxsum,right.maxsum))));
    return result;

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,q,j;
    cin>>n;
    vector<ll>v(n);
    
    for(i=0;i<n;i++)cin>>v[i];
    build(v,0,n-1,0);
    cin>>q;
    for(ll k1=0;k1<q;k1++){
        ll ql,qh;
        cin>>ql>>qh;
        node result=query(ql-1,qh-1,0,n-1,0);
       cout<< result.maxsum;
       if(k1!=q-1)cout<<"\n";
    }

}

1 Like