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