Chefres - editorial

general
, , , , ,
21

#include
#include
using namespace std;

struct Interval
{
int start=-1, end=-1;
};

bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start);
}

int main()
{
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
Interval ta[n+1]={{-1,-1}};
int ta_len=1;
for(int i=1;i<n+1;i++)
{
int x,y;
cin>>x>>y;
ta[i].start=x;ta[i].end=y;
ta_len++;
}
sort(ta, ta+ta_len, compareInterval);

	int ca[m+1]={-1};
	int new_ca[m+1]={-1};
	int maxv=-1;
	int ca_len=1;
	for(int i=1;i<m+1;i++)
	{
		int temp;
		cin>>temp;
		if (maxv<temp)
			maxv=temp;
		ca[i]=temp;
		new_ca[i]=temp;
		ca_len++;
	}
	
	sort(new_ca,new_ca+ca_len);
	
	ca_len--;
	int sol[maxv+1]={0};
	int j=1;
	int i=1;
	while(i<ta_len)
	{
		if (ta[i].start <= new_ca[j] && new_ca[j] < ta[i].end)
		{
			sol[new_ca[j]]=0;
			j++;
		}
		else if(ta[i-1].end <= new_ca[j] && new_ca[j] < ta[i].start)
		{
			sol[new_ca[j]]=ta[i].start-new_ca[j];
			j++;
		}
		else if(new_ca[j]>=ta[i].end)
			i++;
	}
	
	if (j<ca_len+1)
	{
		for(int i=j;i<ca_len+1;i++)
		{
			sol[new_ca[j]]=-1;
			j++;
		}
	}
	
	for(int i=1;i<=ca_len;i++)
		cout<<sol[ca[i]]<<endl;
}

}

what is wrong with my code? it’s complexity is nlogn (I think so) so why it is giving TLE

22

why my binary approach solution is giving tle. i think it’s complexity is nlogn.
Also,please suggest some cases for which my code is giving WA.

23

Can anyone tell me why my BS approach gives TLE but sorting queries approach does not. Both solutions have the same complexity. Both solutions here -
BS - https://pastebin.com/PyhCsSj0
Sorting queries - https://pastebin.com/D5QV9TJH

24

Hey. So this question i had solved in java on the contest day, and the submission from that day is
here. And today, after fruitlessly racking my brain for where the NZEC could have arised, i submitted the same code, and you know it, it showed full AC. Today’s code is here. So what did actually transpire by on the contest day? I am totally perplexed and an answer would be so satisfying.

25

My [solution][1] during contest got 30 pts with a WA for second test and the same


[2] in practice got AC(100 pts). 
This seems to be a bug as [this comment][3] is also similar and I am getting weird results in other problems too. 

  [1]: https://www.codechef.com/viewsolution/20374448
  [2]: https://www.codechef.com/viewsolution/20442402
  [3]: https://discuss.codechef.com/questions/136251/chefres-editorial/136345
26

So why my solution got WA for rest of 70 points during the contest.

27

You’re passing on the vector in int binarysearch(vector<pair<ll,ll> > v1,ll l,ll r,ll key) by value, so you copy a vector of pairs for every single call to binary search. Make that a reference int binarysearch(vector<pair<ll,ll> > &v1,ll l,ll r,ll key) and you should get decent running times.

28

You’re passing the vector by value in your binary search. That by itself is O(n). Pass it by reference.

29

I am using binary search and also pass my vector by reference, still got tle. Please help me, what could i do to decrease the time?
Here is my solution link - https://www.codechef.com/submit/complete/20938161. Please help.