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 ?
You handle duplicate elements incorrectly.
1 Like
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).
5 Likes
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.
1 Like
As the property of set it contains only unique elements, but in this case we need a multiset as y coordinates of two different points may be same. So I guess he adds another increasing counter element tk to make the whole pair unique, as the second element is increasing in each iteration.
BTW you can get ordered multiset just by changing the comparator from less<int> to less_equal<int> so that you don’t need the second element of the pair.
Here in this code:
1 Like
bool by_rml(const qq &a, const qq &b) {
return (a.r - a.l) < (b.r - b.l);
}
This code signifies that you are sorting all the triangle according to altitude.
Now you are using sweep line and traversing sorted y-coordinates and inserting all the points x-y and x+y in two ordered sets.
xmy.insert(points[i].x - points[i].y);
xpy.insert(points[i].x + points[i].y);
And finally now you are playing with slopes ,means you are finding all the points x+y<r+1 (all the points strictly less than from slanting height r+1) and x-y<l (all the points strictly less that from the slanting height l i.e the slope>1) and you are subtracting them to get no of points inside or on the lines of triangle.
ans[qry.index] = xpy.order_of_key(qry.r + 1) - xmy.order_of_key(qry.l);
Am i right??
2 Likes