" You can solve this problem using Binary Indexed Trees." (copied from spoj forum)
On Mon, Mar 21, 2011 at 3:09 PM, Terence <technic....@gmail.com> wrote: > In this problem, sum can be as large as 50000*10^9. > Try breaking the whole interval into several stages (no more than 2*N), > each with a fixed amount of tasks. > Then in each stage, the schedule is a simple loop: A B C D E A B C D E A B > ... > Process each stage in O(1) time, then the total time complexity is O(N). > > > > On 2011-3-21 17:32, saurabh singh wrote: > > using scanf and printf and still tle,I am not pretty sure how malloc or new > arrays can speed up execution? > > On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal <sm14it...@gmail.com>wrote: > >> use scanf n printf instead of cin n cout, >> malloc array of structures after reading value of n if working in c else >> use new in cpp >> rest i guess...is ok >> On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal <ankitsamb...@gmail.com >> > wrote: >> >>> I worked on this problem but cud not get a more efficient algo than >>> yours. >>> Plz get back 2 me if u find a better algo. >>> >>> >>> On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma < >>> akshatasharm...@gmail.com> wrote: >>> >>>> I tried to solve this problem >>>> https://www.spoj.pl/problems/RRSCHED/ >>>> >>>> I am getting TLE!! How can I improve my code?? >>>> >>>> #include<iostream> >>>> #include<stdio.h> >>>> >>>> using namespace std; >>>> >>>> struct process >>>> { >>>> long time; >>>> int finished; >>>> long elapsed_time; >>>> }; >>>> >>>> int main() >>>> { >>>> long n,sum=0; >>>> cin>>n; >>>> struct process prss[50000]; >>>> for(long i=0;i<n;i++) >>>> { >>>> scanf("%ld",&prss[i].time); >>>> prss[i].finished=0; >>>> sum+=prss[i].time; >>>> } >>>> long index=0; >>>> for(long k=1;k<=sum;k++) >>>> { >>>> while(prss[index].finished==1) >>>> index++; >>>> >>>> prss[index].time--; >>>> >>>> if(prss[index].time==0) >>>> { >>>> prss[index].finished=1; >>>> prss[index].elapsed_time=k; >>>> } >>>> >>>> index++; >>>> if(index==n) >>>> index=0; >>>> } >>>> >>>> for(long i=0;i<n;i++) >>>> printf("%ld\n",prss[i].elapsed_time); >>>> 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. >>> >> >> >> >> -- >> Sanchit Mittal >> Second Year Undergraduate >> Computer Engineering >> Delhi College of Engineering >> ph- +919582414494 >> >> -- >> 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. >> > > > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD > > > -- > 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. > -- regards, chinna. -- 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.
