i am getting wa for https://www.spoj.pl/problems/FREQUENT/
here is my code i have used segment trees it would be great if someone
could give me a test case for which my code gives wa.
Thanks in advance.
#include<iostream>
#include<vector>
#include<fstream>
#include<math.h>
#include<string.h>
#include<stdio.h>
using namespace std;
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int min(int a,int b)
{
if(a<b)return a;
return b;
}
template<class T>
class SegmentTree
{
int **A,size;
public:
SegmentTree(int N)
{
int x = (int)(ceil(log(N)/log(2)));
size = 2*(int)pow(2,x);
A = new int*[size];
for(int x=0;x<size;x++)
A[x]=new int[4];
for(int x=0;x<size;x++)
{
for(int y=0;y<4;y++)
A[x][y]=-1;
}
}
void initialize(int node, int start,
int end, vector<int>v1,vector<int>v2,vector<int>v3)
{
if (start==end)
{A[node][0] =
v1[start];A[node][2]=v2[start];A[node][3]=v3[start];A[node][1]=-1;}
else
{
int mid = (start+end)/2;
initialize(2*node,start,mid,v1,v2,v3);
initialize(2*node+1,mid+1,end,v1,v2,v3);
if (A[2*node][3]>=
A[2*node+1][3])
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node][3];}
else
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node+1][3];}
}
}
// void pr()
// {
// for(int x=1;x<size;x++) cout<<"x="<<x<<" "<<A[x][0]<<"
"<<A[x][1]<<" "<<A[x][2]<<" "<<A[x][3]<<"\n";
// }
int query(int node,int i, int j)
{
// cout<<"node="<<node<<" i="<<i<<" j="<<j<<"\n";
if (i>A[node][2] || j<A[node][0])
{return -1;}
else if (A[node][1]==-1&&j<=A[node][2]&&i>=A[node][0])
{int
ss=max(i,A[node][0])-A[node][0];ss=ss+A[node][2]-min(j,A[node][2]);return
(A[node][3]-ss);}
else
{ int id1=-1,id2=-1;
if(i<=A[node][1])
id1 = query(2*node,i,min(j,A[node][1]));
if(A[node][1]<j)
id2 = query(2*node+1,max(i,A[node][1]+1),j);
//cout<<"node="<<node<<"id1="<<id1<<"id2="<<id2<<"\n";
if (id1==-1)
return id2;
if (id2==-1)
return id1;
if (id1>=id2)
return id1;
else
return id2;
}
}
};
int main()
{
int i,j,N;
int A[100006];
scanf("%d",&N);
int M;
scanf("%d",&M);
for (i=0;i<N;i++)
scanf("%d",&A[i]);
vector<int>v1;
vector<int>v2;
vector<int>v3;
int ini=A[0],now,count=1,ip=0;
for(int x=1;x<N;x++)
{
now=A[x];
if(now==ini)
count++;
else{ini=A[x];v1.push_back(ip);v2.push_back(x-1);v3.push_back(count);count=1;ip=x;}
}
v1.push_back(ip);v2.push_back(N-1);v3.push_back(count);
int sz=v1.size();
SegmentTree<int> s(sz);
s.initialize(1,0,sz-1,v1,v2,v3);
for(int x=0;x<M;x++)
{
(scanf("%d%d",&i,&j));
printf("%d\n",s.query(1,i-1,j-1));
}
int tmp;
cin>>tmp;
return(0);
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
