Please have a look at this page: http://www.informatik.uni-ulm.de/acm/Locals/2007/input/. It contains input data for the problem.
On 21 окт, 00:39, ANUJ KUMAR <kumar.anuj...@gmail.com> wrote: > i am getting wa forhttps://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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
