please give me its output file also so that i can check mine On 10/21/10, ANUJ KUMAR <[email protected]> wrote: > 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.
