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);↵
}↵
↵
↵
// ll fib(ll n){↵
↵
// if(n==0){↵
// return 0;↵
// }↵
↵
// if(n==1 || n==2)↵
// {↵
// return 1;↵
// }↵
↵
// if(n%2==0){↵
// k=n/2;↵
// return (2*fib(k-1)+fib(k))*fib(k);↵
// }↵
// return fib(k)*fib(k)+fib(k-1)*fib(k-1);↵
// }↵
↵
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;↵
}↵
↵
}↵
~~~~~↵
↵
↵
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);↵
}↵
↵
// ll fib(ll n){↵
↵
// if(n==0){↵
// return 0;↵
// }↵
↵
// if(n==1 || n==2)↵
// {↵
// return 1;↵
// }↵
↵
// if(n%2==0){↵
// k=n/2;↵
// return (2*fib(k-1)+fib(k))*fib(k);↵
// }↵
// return fib(k)*fib(k)+fib(k-1)*fib(k-1);↵
// }↵
↵
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;↵
}↵
↵
}↵
~~~~~↵
↵
