same here bro! i also use condition x-y>=l and in all those points with using bit i try to find all those point with x-y<=r,but still getting wrong ans
1 Like
It will time out right?
1 Like
Sort on one inequalty say x-y and use BIT to handle other inequality
1 Like
Yes that would have worked for 50pts I think, since height remains constant. You can eliminate all the points above the height of the triangle and do this
Small fix: the closing dollar sign is missing on the time complexity
Thanks for the tip of multiplying all coordinates by 2! (not doing that made my sol so much more complicated)
3 Likes
Same approach with BIT was TLEing 
Intersection of two the regions should area of the triangle and its extended sector below y axis so I was hoping for a complete solution through this method rather than a subtask.
If this is what you mean, you would be missing out on points in area ‘d’.
That is why I said one could have got 50 on this by eliminating points above the triangle height
D won’t satisfy r-y-x>=0
@taran_1407 can’t this be solved using mo’s algorithm?
sort all the points according to x value
for any query l,r we can first determine the index in arrays such that L=i and R=j and a[L].x_value >=l and a[R].x_value<=r using binary search.
After modifying the queries we can use mo’s I think, where for each modified query we need to find the number of points in the interval L-R such that the slope is ±1 from original l and r.
You will be getting a+b and a+c by using line equations right?
yes
How do u plan to find a?
Rotating the axes 90 degrees clockwise and scaling the coordinates by 2*sqrt(2) makes the coding part much easier.
The equation of left side of triangle will be x-y = l and right side will be x+y = r.
So sorted all points on x-y. Also sorted all queries. Now starting from the right most queries, I put all points with x-y>=l in ordered_set. Then find the number of points having x+y less than r+1 in ordered_set.
Why does this solution get WA?
You can’t find a by
(a+b)+(a+c) - n
Because that’s what I tried to do
Sort on y-x and use binary search to get all solutions to l+y-x<=0 then for this range use BIT to find solutions for r-x-y>=0 .Isse Intersection aa jana chahiye tha pata nhi kya gadbad ho ri hai
Why are there so tough time limit constraints for question TRIQRY. There can be approaches using c++ inbuilt ordered_set but due to strict time limit those solutions can only pass partially. I request the problem setters to keep N around 100000 when they are expecting a O(NlogN) solution especially when there may be segment tree in approach as there is a set of problems which can be solved with segment tree and set both!
5 Likes
Okay… I don’t know much about BIT
Probably you made some implementation errors