Why im getting TLE ....plz tell me a way to optiomise this code

general
,
1

i dont want answer all i want to know is the feww ways to optimize the code which i think is best possible way for a noob like me

Screenshot (329)
Screenshot (329)458×845 37.1 KB

,for your understanding im posting this question)

and here is my code …im not sure u will understand but u have 2…thats what programmers do…

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

int main(void) {
int a,b;
scanf("%d",&a);
for(b=0;b<a;b++)
{
int d,c,x,j;
scanf("%d%d",&d,&c);
int v=d+1;
intarr=(int)calloc(v,sizeof(int));

    for(x=0;x<c;x++)
    {
        int l,r,y,i,z;
        
        scanf("%d%d",&l,&r);
        z=r-l;
        for(y=0,i=1;y<=z;y++)
        {
            arr[l]+=i;
           
			l++;
            i++;
        }
    }
 for(j=1;j<=d;j++)
 printf("%d ",arr[j]);
 printf("\n");
 }

}

2

hi, you’re getting TLE because your code runs in O(N^2) in worst case , with the constrait 1 <= N <= 10^5 there isn’t enough time, you should consider using sweep line

2 Likes
3

first of all a great thanks for your consideration and 2nd could u plz share what is sweep and how would i use it

4

See this article about difference arrays. This problem uses the same concept. Basically, you need to do the updates in O(1) time, and then post-process afterwards to get the final array. You can also look at my solution and see if that helps.

1 Like
5

This post was flagged by the community and is temporarily hidden.

6 
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
	int n,q;
	cin>>n>>q;
	vector<int> A(n+2),B(n+2);
	for(int i=0;i<q;i++)
	{
		int l,r;
		cin>>l>>r;
		A[l]-=l-1;
		A[r+1]+=l-1;
		B[l]++;
		B[r+1]--;
	}
	for(int i=1;i<=n;i++)
	{
		B[i]+=B[i-1];
		A[i]+=A[i-1];
	}
	for(int i=1;i<=n;i++)
	{
		A[i] += B[i]*i;
		cout<<A[i]<<" ";
	}
	cout<<"\n";

  }
}

I hope this helps!

7

You should format your code

8

woowwww thats the answer i was searching for…bruhhhh…literally dude…