Memory Limit Exceeded

Revision en2, by redgulli, 2020-04-07 20:10:57

I am trying out this problem on Hackerearth, I am getting Memory Limit Exceeded. I am using Segment Trees and I don't know where to optimize.

https://www.hackerearth.com/challenges/hiring/Samsung-R-D-Institute-Hiring-Challenge/algorithm/fibonacci-with-gcd-16/description/

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

void build(vector<int>&tree,vector<int>A,ll node, ll start, ll end){
	if(start==end){
		tree[node]=A[start];
        return;
	}
	ll mid=start+(end-start)/2;
	build(tree,A,2*node,start,mid);
	build(tree,A,2*node+1,mid+1,end);
	tree[node]=__gcd(tree[2*node],tree[2*node+1]);
}


ll query(vector<int>tree,ll node, ll start, ll end, ll left, ll right){
	if(start >right|| end <left )
		return 1;
	
	if(start>=left && right<=end){
		// this node is completely within the range
		// return it as a partial answer
		return tree[node];
	}
	ll mid=start+(end-start)/2;
	int leftAnswer=query(tree,2*node,start,mid,left,right);
	int rightAnswer=query(tree,2*node+1,mid+1,end,left,right);
	return __gcd(leftAnswer,rightAnswer);
}

int main(){
	ll N,Q;
	cin>>N>>Q;
    vector<int>tree(2*N+1);
	vector<int>A(N+1);
	for(ll i=1;i<=N;i++) {
		cin>>A[i];
	}

	build(tree,A,1,1,N);

	for(ll i=0;i<Q;i++){
		ll left,right;
		cin>>left>>right;
		ll index=query(tree,1,1,N,left,right);
		cout<<index<<endl;
	}

}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English redgulli 2020-04-07 20:10:57 247
en1 English redgulli 2020-04-07 17:51:59 1707 Initial revision (published)