Doubt on the question:MAX QUERY-1

#1

#include
#define ll long long
using namespace std;

void buildTree(ll a,ll beg,ll end,ll tree,ll idx,ll k)
{
if(beg==end)
{
if(a[beg]>=k)
{
tree[idx]=1;
}
else
{
tree[idx]=0;
}
return;
}
ll mid=(beg+end)/2;
buildTree(a,beg,mid,tree,2idx,k);
buildTree(a,mid+1,end,tree,2idx+1,k);

tree[idx]=tree[2*idx]+tree[2*idx+1];

}
ll query(ll tree,ll beg,ll end,ll l,ll r,ll idx)
{
if(r<beg || l>end)
{
return 0;
}
if(l<=beg && r>=end)
{
return tree[idx];
}
ll mid=(beg+end)/2;
ll leftAns=query(tree,beg,mid,l,r,2idx);
ll rightAns=query(tree,mid+1,end,l,r,2*idx+1);

return leftAns+rightAns;

}
int main()
{
ll n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];

ll t;
cin>>t;
while(t--)
{
	ll p,q,k;
	cin>>p>>q>>k;
	ll tree[4*n+1];
	p--;
	q--;
	buildTree(a,0,n-1,tree,1,k);
	cout<<query(tree,0,n-1,p,q,1)<<endl;
}

}
WHY i am getting tle??
how can i optimise this code??

#2

Use segment tree with each node as a policy based data structure. Complexity will be O(n (log(n)^2)) but it will work.

#3


You can have a look at my code here

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

@Jun18APP0015
merge (segTree[v2].begin(), segTree[v2].end(), segTree[v2+1].begin(), segTree[v2+1].end(),
back_inserter (segTree[v]));

above code is equivalent to
segTree[v] = segTree[2v] + segTree[2v+1]

am i right ?

#6

merge (segTree[v2].begin(), segTree[v2].end(), segTree[v2+1].begin(), segTree[v2+1].end(),
back_inserter (segTree[v]));
This means merging like we do in merge sort!
All elements of 1st and 2nd arrays are merged.

segTree[v] = segTree[2v] + segTree[2v+1]
This means just adding 2 elements and saving at index v.

Please go through documentation of inbuilt merge once.

1 Like