In STFM (february challenge 2015) i am getting tle for the first subtask , rest all the subtasks are accepted.What should I do?

general
1

#include <stdio.h>
#include <stdlib.h>

unsigned long long int m=0;

void quicksort(unsigned long long int [],unsigned long long int,unsigned long long int);

 
int main()

{
    unsigned long long int p[100002],sum1=0ULL,sum2=0ULL,sum3=0ULL,sum4=0ULL,i,j,k,ans,count,n,fact;

scanf("%llu %llu",&n,&m);

 p[0]=0ULL;

for(i=1ULL;i<=n;i++)

scanf("%llu",&p[i]);

quicksort(p,1ULL,n);

fact=1ULL;
        
       
        
for(i=1ULL;i<=n;i++)

{

for(j=p[i-1]+1ULL;j<=p[i] && j<m;j++)

{
          

 fact=((fact%m)*(j%m))%m;

sum1+=((j%m)*fact)%m;
            
}
 

if(p[i]%2==0)

sum2=((p[i]%m)*((((p[i]/2)%m)*((p[i]+1)%m))%m))%m;

else

sum2=((p[i]%m)*(((p[i]%m)*(((p[i]+1)/2)%m))%m))%m;
       
        
       

sum3=(sum1+sum2)%m;
        

for(k=i+1ULL,count=1ULL;p[k]==p[i] && k<=n;k++)

 {

 count++;

}

sum4=sum4+sum3*count;   

i=k-1ULL;
 

}

 ans=sum4%m;

 printf("%llu\n",ans);
 
        
 
 
    return 0;
}
 
void quicksort(unsigned long long int x[],unsigned long long int first,unsigned long long int last){

unsigned long long int pivot,j,i;

unsigned long long int temp;
 
     if(first<last){
         pivot=first;
         i=first;
         j=last;
 
         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }
 
         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);
 
    }
2

Check if(p[i] <=6){
then apply brute force ;}

1 Like
3

I would suggest going for merge sort. Quick sort is better than merge in best case but even insertion sort is better than quick sort in worst case. Merge sort always has O(nlogn) complexity.