Its better to write an O(n) solution for this problem as the # test cases are very high and #elements are also very huge.. use visited array for distinct numbers ... space--O(n).. time--O(n)
On Sat, Aug 25, 2012 at 2:39 AM, michael miller < wentworth.miller6...@gmail.com> wrote: > Hi, > You are given N numbers. You have to perform two kinds of operations: > U x y - x-th number becomes equal to y. > Q x y - calculate the sum of distinct numbers from x-th to y-th. It means > that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7). > > 1<=N<=50000 and > t is the number of test cases where 1<=t<=100000 > > all numbers fit in the 32 bit integer range... > > suggest some solution.. > > here is my solution > but it is giving wrong answer fo some unknown test case...plz suggest me > the test case where i am getting wrong answer.... > > > #include<stdio.h> > #include<math.h> > int main() > { > int list[50000],i,n,j,sum,k,l;char c;long t; > scanf > <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%d",&n); > for(i=0;i<n;i++) > { > scanf > <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%d",&list[i]); > } > scanf > <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%ld",&t); > t=2*t; > while(t) > { > sum=0; > scanf > <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%c",&c); > fflush(stdin); > scanf > <http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html>("%d > %d",&k,&l); > if(c=='Q') > { > for(i=k-1;i<l-1;i++) > { > for(j=i+1;j<l;j++) > { > if(list[i]==list[j]) > break; > else if((j==l-1) &&(list[i]!=list[j])) > { > sum=sum+list[i]; > > } > } > } > > printf > <http://www.opengroup.org/onlinepubs/009695399/functions/printf.html>("%d\n",sum+list[l-1]); > } > if(c=='U') > { > list[k-1]=l; > > } > t--; > } > 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 algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.