thanks On 10/21/10, juver++ <[email protected]> wrote: > 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 <[email protected]> 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 [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. > >
-- 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.
