Gss1

[pikkupr]

Getting "runtime error (SIGSEGV) " error and i'm not getting the problem... can anyone help me to solve it ..

#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
#define ll long long
int sn,arr[MAX];
struct node{
	ll best,sum,lft,ryt;
	node(ll a){
		best = sum = lft = ryt = a;
	}
	void merge(node a,node b){
		sum = a.sum+b.sum;
		lft = max(a.lft, a.sum+b.lft);
		ryt = max(b.ryt, a.ryt+b.sum);
		best = max(sum, max(lft,ryt) );
	}
}*segtree=NULL;
ll query(int i,int j,int ri,int rj,int curr){
	if(rj<i || ri>j)
		return 0;
	if(ri<=i&&rj>=j)
		return segtree[curr].best;
	int mid = i + (j-1)/2,l=2*curr+1;
	return query(i,mid,ri,rj,l) + query(mid+1,j,ri,rj,l+1);
}
void build(int i,int j,int curr){
	if(i==j){
		segtree[curr] = node(arr[i]);
		return;
	}
	int l = 2*curr+1,r,mid=i +(j-i)/2;
	r = 2*curr+2;
	build(i,mid,l);
	build(mid+1,j,r);
	segtree[curr].merge(segtree[l],segtree[r]);
}
void init(int n){
	sn = ceil(log2(n)+1);
	sn = 2*pow(2,sn);
	segtree = (node*)malloc(sn * sizeof(node));
	build(0,n-1,0);
}
int main() {
	int n,q,ri,rj;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	init(n);
	build(0,n-1,0);
	cin>>q;
	while(q--){
		cin>>ri>>rj;
		cout<<query(0,n-1,ri-1,rj-1,0)<<'\n';
	}
	free(segtree);
	return 0;
}

thanks for the help!!

[leppyr64]

int mid = i + (j-1)/2

[pikkupr]

Still in shock 4r making mistake lyk dat ..

@leppy : thnks for the help..

but now it's showing wrong answer ...

[leppyr64]

Happy to help. Work with it a bit. Post your updated code if you can't figure it out.

[pikkupr]

managed to avoid WA but now got stuck on TLE ...

#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
#define ll long long
int sn,arr[MAX];
struct node{
    ll best,sum,lft,ryt;
	node(ll a = 0){
		best = sum = lft = ryt = a;
	}
	void merge(node a,node b){
		sum = a.sum+b.sum;
		lft = max(a.lft, a.sum+b.lft);
		ryt = max(b.ryt, a.ryt+b.sum);
		best = max(sum, max(lft,ryt) );
	}
}*segtree=NULL;
node query(int i,int j,int ri,int rj,int curr){
	if(rj<i || ri>j)
		return node();
	if(ri<=i&&rj>=j)
		return segtree[curr];
	int mid = i + (j-i)/2,l=2*curr+1;
    node a,b,temp;
	a = query(i,mid,ri,rj,l);
    b = query(mid+1,j,ri,rj,l+1);
    temp.merge(a,b);
    return temp;
}
void build(int i,int j,int curr){
	if(i>j)
		return;
	if(i==j){
		segtree[curr] = node(arr[i]);
		return;
	}
	int l = 2*curr+1,mid=i +(j-i)/2,r = 2*curr+2;
	build(i,mid,l);
	build(mid+1,j,r);
	segtree[curr].merge(segtree[l],segtree[r]);
}
void init(int n){
	sn = ceil(log2(n)+1);
	sn = 2*pow(2,sn);
	segtree = (node*)malloc(sn * sizeof(node));
	build(0,n-1,0);
}
int main() {
	int n,q,ri,rj;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	init(n);
	build(0,n-1,0);
	cin>>q;
	while(q--){
		cin>>ri>>rj;
		node temp = query(0,n-1,ri-1,rj-1,0);
        cout<<temp.best<<'\n';
	}
	free(segtree);
	return 0;
}

can you improve this code?? thnks for it!!

[leppyr64]

Cin/cout are slow.

[pikkupr]

used scanf & printf .. now it's giving wrong answer

[leppyr64]

If you're still having an issue, please post your updated code and edit the previous posts and remove the code.

[pikkupr]

here's the updated code:

#include <bits/stdc++.h>
using namespace std;
#define MAX 50005
#define ll long long
int sn,arr[MAX];
struct node{
    ll best,sum,lft,ryt;
	node(ll a = 0){
		best = sum = lft = ryt = a;
	}
	void merge(node a,node b){
		sum = a.sum+b.sum;
		lft = max(a.lft, a.sum+b.lft);
		ryt = max(b.ryt, a.ryt+b.sum);
		best = max(a.ryt+b.lft, max(a.best,b.best));
	}
}*segtree=NULL;
node query(int i,int j,int ri,int rj,int curr){
	if(rj<i || ri>j)
		return node();
	if(ri<=i&&rj>=j)
		return segtree[curr];
	int mid = i + (j-i)/2,l=2*curr+1;
	if(j<=mid)
		return query(i,j,ri,rj,l);
	else if(i>mid)
		return query(i,j,ri,rj,l+1);
	else{
    	node a,b,temp;
		a = query(i,mid,ri,rj,l);
    	b = query(mid+1,j,ri,rj,l+1);
    	temp.merge(a,b);
	    return temp;
	}
}
void build(int i,int j,int curr){
	if(i>j)
		return;
	if(i==j){
		segtree[curr] = node(arr[i]);
		return;
	}
	int l = 2*curr+1,mid=i +(j-i)/2,r = 2*curr+2;
	build(i,mid,l);
	build(mid+1,j,r);
	segtree[curr].merge(segtree[l],segtree[r]);
}
void init(int n){
	sn = ceil(log2(n)+1);
	sn = 2*pow(2,sn);
	segtree = (node*)malloc(sn * sizeof(node));
	build(0,n-1,0);
}
int main() {
	int n,q,ri,rj;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	init(n);
	build(0,n-1,0);
	scanf("%d",&q);
	while(q--){
		scanf("%d %d",&ri,&rj);
		node temp = query(0,n-1,ri-1,rj-1,0);
        printf("%lld\n",temp.best);
	}
	free(segtree);
	return 0;
}

[leppyr64]

Why do you run build twice?

[imdaredevil]

#include
using namespace std;
int main()
{
int n;
cin>>n;
int a[2n + 1];
for(int i=0;i<n;i++)
cin>>a[n+i];
for(int i=n-1;i>=1;i–)
a[i] = max(a[2i],a[2*i + 1]);
int q;
cin>>q;
for(;q>0;q–)
{
int l,r;
cin>>l>>r;
l–;
int res = a[n+l];
for(l+=n,r+=n ; l<r && l>=1 && r>1;l/=2,r/=2)
{
if(l%2 != 0)
{
res = max(res,a[l]);
l++;
}
if(r%2 != 0)
{
r–;
res = max(res,a[r]);
}
}
cout<<res<<"\n";
}
return 0;

}

Can anyone debug my code,. Got WA.