# 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

@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

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