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
had made a silly in implementation AC aa gaya 
1 Like
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
1 Like
You can process queries off-line and can use Fenwick tree instead of Merge sort tree.
1 Like
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.
2 Likes
#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 ?