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!
Okay… I don’t know much about BIT
Probably you made some implementation errors
had made a silly in implementation AC aa gaya 
I tried segment tree but got TLE on second sub-task although I hoped it should have worked. Are any optimizations possible or is the approach just wrong?
Using a 4n size array would definitely hurt, give n\leq10^6. You should use the 2n segment tree.
You can see here how I implemented a 2n segment tree.
https://www.codechef.com/viewsolution/32284821
You can process queries off-line and can use Fenwick tree instead of Merge sort tree.
Soo true the time constraints were too harsh for NLogN solutions using ordered set or segment tree.I tried both and did my best to reduce the time constraints but only passed the 1st pre test.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define x first
#define y second
#define pi 3.141592653589793
#define mod 1000000007
#define pb push_back
#define all(v) v.begin(),v.end()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_map;
bool by_y(const pii &a, const pii &b) {
return a.y < b.y;
}
struct qq {
int l, r, index;
};
bool by_rml(const qq &a, const qq &b) {
return (a.r - a.l) < (b.r - b.l);
}
int main() {
fast_io;
tc {
int n, q;
cin >> n >> q;
vii points(n);
for (int i = 0;i < n;i++)
cin >> points[i].x >> points[i].y;
sort(all(points), by_y);
ordered_multiset xmy, xpy;
vector<qq> qarr(q);
for (int i = 0;i < q;i++) {
cin >> qarr[i].l >> qarr[i].r;
qarr[i].index = i;
}
sort(all(qarr), by_rml);
vi ans(q);
int i = 0;
for (auto &qry : qarr) {
while (i < n && 2 * points[i].y <= qry.r - qry.l) {
xmy.insert(points[i].x - points[i].y);
xpy.insert(points[i].x + points[i].y);
i++;
}
ans[qry.index] = xpy.order_of_key(qry.r + 1) - xmy.order_of_key(qry.l);
}
for (auto el : ans)
cout << el << ' ';
cout << '\n';
}
}
Link of the solution CodeChef: Practical coding for everyone
This solution looks easy to understand ,done using ordered set
Here y values of points are sorted in increasing order, and the triangles are sorted according to hypotenuse in ascending order.
but i did not understand this line 2 * points[i].y <= qry.r - qry.l
while (i < n && 2 * points[i].y <= qry.r - qry.l)
can anyone help me pls ?
You handle duplicate elements incorrectly.
How about making life easier by just rotating all the points by 45 degree CCW. This takes line x=0 to x=y. Thus the problem simply gets converted to count number of points in a square. It’s important to note that diagonal is always x=y and there are no points with negative co-ordinates initially hence we can take entire square.
Now this becomes a standard problem with two pointer and a DS (BIT, segment Tree, PBDS).
Now how to rotate the entire thing by 45 degree?
Standard formulae
x’= xcos(t) - ysin(t)
y’= xcos(t) + ysin(t).
where (x’,y’) are new co-ordinates after rotation and (x,y) are initial co-ordinates.
thus
x’= x-y
y’=x+y
Implementation Note:
If you are using BIT or Segment Tree make sure to shift (by 1e6 works) indices as after rotation some of them may be negative (No need for co-ordinate compression).
Can you provide some resources for this standard problem(number of points in a square)? Are the queries handled offline?
I just learnt BIT
Thanks. Got it.
Points with y-coordinate higher than (r_i-l_i)/2 will never be in the triangle.
@rahul_g
while inserting in ordered_set, you have written
“s.insert({a[ptr].second, tk++});”.
What is the significance of tk++?
Given that I am querying by using ({r+1,-1}), can we not insert directly by :
“s.insert({a[ptr].second, 1});”?
I tried doing that but got WA. Why?
It ensures that s counts different points with same value as unique.