Segment tree doubt

Can someone please help me with this question .

Given 3 arrays(a,b,c) of size n and q queries . For each query there will be 3 ranges (l1,r1 of Array a) ,(l2,r2 of Array b) (l3,r3 of Array c) . Find the distinct elements of each array in its given range . Merge the results of 3 queries and then print the count of distinct elements

I have written the code but i’m unable to pass the tests . It is giving me runtime error :frowning:

@aman_robotics

Code :

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
void build(bitset<5001> segtree[],int a[],int index,int low,int high)
{
	if(low>high){
		return;
	}
	if(low==high)
	{
		segtree[index][a[low]]=1;
		return;
	}
	int mid=(low+high)/2;
	build(segtree,a,2*index,low,mid);
	build(segtree,a,2*index+1,mid+1,high);
	segtree[index]=segtree[2*index]|segtree[2*index+1];
}
bitset<5001> query(bitset<5001> segtree[],int index,int low,int high ,int qs,int qe)
{
	if(qs>high || qe<low || low>high)
	{
		return 0;
	}
	if(qs<=low && qe>=high)
	{
		return segtree[index];
	}
	int mid=(low+high)/2;
	return query(segtree,2*index,low,mid,qs,qe)|query(segtree,2*index+1,mid+1,high,qs,qe);
}
int main()
{
	int n;
	cin >> n;
	int a[n];
	int b[n];
	int c[n];
	bitset<5001> segtree1[4*n+1];
	bitset<5001> segtree2[4*n+1];
	bitset<5001> segtree3[4*n+1];
	int q,l1,l2,r1,r2,l3,r3;
	for(int i = 0 ; i <n ; i ++ ){
		cin >> a[i];
	}
	for(int i = 0 ; i < n ; i ++ ){
		cin >> b[i];
	}
 	for(int i = 0 ; i < n ; i++ ){
 		cin  >> c[i];
	 }
	build(segtree1,a,1,0,n-1);
	build(segtree2,b,1,0,n-1);
	build(segtree3,c,1,0,n-1);
	cin >> q;
	bitset<5001>b1,b2,b3;
	while(q--)
	{
		cin >> l1 >> r1 >> l2 >> r2 >> l3 >> r3;
		b1=query(segtree1,1,0,n-1,l1-1,r1-1);
		b2=query(segtree2,1,0,n-1,l2-1,r2-1);
		b3=query(segtree3,1,0,n-1,l3-1,r3-1);
		cout<<(b1|b2|b3).count()<<'\n';
	}
}
1 Like

What are the constraints?

@aman_robotics Sorry for not mentioning the constraints ! n value is atmost 5000 , the array values are atmost 5000 and queries are atmost 10^6

Can u provide the question link…

1 Like

Actually , this question is from yesterday’s codevita . So , I don’t have link currently :frowning:

Idea seems ok to me. Maybe some implementation issue which I don’t get any looking at the code.
Maybe memory limit is less for Codevita which is why RTE.

1 Like