Hey, this is my code for spoj frequent using segment tree but it’s giving me WA on when I submitted on spoj. When I checked with test cases I’m getting the correct output. I don’t what’s wrong in my code.
For each node what I have taken is lower limits value and its frequency and higher limits value and frequency and max frequency in the given range of each node.
#include<bits/stdc++.h>
using namespace std;
class JustNode{
public:
pair<int,int> freqR,freqL;
int freqMax;
void specifyNode(JustNode &leftNode,JustNode &rightNode){
freqL.first = leftNode.freqL.first;
freqL.second = leftNode.freqL.second;
freqR.first = rightNode.freqR.first;
freqR.second = rightNode.freqR.second;
freqMax = max(leftNode.freqMax,rightNode.freqMax);
if(leftNode.freqR.first==rightNode.freqL.first){
if(freqL.first==leftNode.freqR.first){
freqL.second = leftNode.freqR.second + rightNode.freqL.second;
}
if(freqR.first==leftNode.freqR.first){
freqR.second = leftNode.freqR.second + rightNode.freqL.second;
}
freqMax = max(freqMax,leftNode.freqR.second + rightNode.freqL.second);
}freqMax= max(max(freqMax,freqL.second),freqR.second);
}
void setValue(int value){
freqMax = 1;
freqR.first = value;
freqR.second = 1;
freqL.first = value;
freqL.second = 1;
}
};
void buildSegment(JustNode val,int arr,int llimit,int hlimit,int node){
if(llimit>hlimit) return;
if(llimit==hlimit){
val[node-1].setValue(arr[llimit]);
return;
}
int mid = (llimit+hlimit)/2;
buildSegment(val,arr,llimit,mid,2node);
buildSegment(val,arr,mid+1,hlimit,2node+1);
val[node-1].specifyNode(val[2node-1],val[2node]);
return;
}
JustNode queryNode(JustNode *val,int llimit,int hlimit,int start,int end,int node){
if(llimit>hlimit || llimit>end || hlimit<start){
JustNode justval;
justval.freqMax = 0;
justval.freqL.first =0;
justval.freqL.second = 0;
justval.freqR.first = 0;
justval.freqR.second = 0;
return justval;
}
// cout << llimit << " "<< hlimit << " "<< start << " "<< end<<endl;
if(llimit>=start && hlimit<=end){
// cout << val[node-1].freqMax.first << " "<< val[node-1].freqMax.second<< endl;
return val[node-1];
}
int mid = (llimit+hlimit)>>1;
JustNode leftNode = queryNode(val,llimit,mid,start,end,2*node);
JustNode rightNode = queryNode(val,mid+1,hlimit,start,end,2*node+1);
JustNode returNode;
returNode.freqL.first = leftNode.freqL.first;
returNode.freqL.second = leftNode.freqL.second;
returNode.freqR.first = rightNode.freqR.first;
returNode.freqR.second = rightNode.freqR.second;
returNode.freqMax = max(leftNode.freqMax,rightNode.freqMax);
if(leftNode.freqR.first==rightNode.freqL.first){
if(returNode.freqL.first==leftNode.freqR.first){
returNode.freqL.second = leftNode.freqR.second + rightNode.freqL.second;
}
if(returNode.freqR.first==leftNode.freqR.first){
returNode.freqR.second = leftNode.freqR.second + rightNode.freqL.second;
}
returNode.freqMax = max(returNode.freqMax,leftNode.freqR.second + rightNode.freqL.second);
}
returNode.freqMax = max(max(returNode.freqMax,returNode.freqL.second),returNode.freqR.second);
return returNode;
}
int main(){
int n,q;
cin >> n >> q;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int arr[n];
for(int i =0;i<n;i++){
cin >> arr[i] ;
}
JustNode bval[n*4+2];
buildSegment(bval,arr,0,n-1,1);
while(true){
int start,end;
cin >> start;
if(start==0) break;
cin >> end;
JustNode jnode = queryNode(bval,0,n-1,start-1,end-1,1);
// cout <<jnode.freqR.first<<" "<< jnode.freqL.first <<" "<<jnode.freqMax.first << endl;
cout << jnode.freqMax << endl;
}
return 0;
}