What could be optimised in this code? The algo is correct, I am getting a TLE.
I have used the fact that point lying on the same side of a line have same (+,-) sign when put in the line’s equation.
So, the mid point of base and the points inside the triangle would give same + or - sign when put in the line equations
y-x+l
and
y+x-r
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test;
cin>>test;
while(test--)
{
int n,q;
cin>>n>>q;
int x[n],y[n];
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
}
int l,r;
while(q--)
{
cin>>l>>r;
int xo=(l+r)/2;
int count=0;
for(int i=0;i<n;i++)
{
if(x[i]>=0)
{
if((l-xo)*(y[i]-x[i]+l)>=0)
{
if((xo-r)*(y[i]+x[i]-r)>=0)
{
count++;
}
}
}
}
cout<<count<<" ";
}
cout<<"\n";
}
}
I used policy based data structure instead of segment tree to find number of elements in a range, and both has time complexity of logn, but I am getting TLE in subtask 2. Can anyone tell why!
Here is my code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define f first
#define s second
#define pb push_back
#define REP(i,a,b) for(long long int i=a ; i<b ; i++)
#define mp make_pair
#define mt make_tuple
#define INF 1000000000000000000
#define mod 1000000007
#define pi pair<ll,ll>
#define pd pair<ld,ld>
#define tp tuple<ll,ll,ll>
#define vi vector<ll>
#define vd vector<ld>
#define vvi vector<vi>
#define vvd vector<vd>
#define vpi vector<pi>
#define vpd vector<pd>
#define us unordered_set<ll>
#define um unordered_map<ll,ll>
#define sortA(a) sort(a.begin(),a.end())
#define sortD(a) sort(a.begin(),a.end(),greater<pi>())
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;
#define in insert
#define fbo find_by_order
#define ook order_of_key
void solve()
{
ll n,q;
cin>>n>>q;
vpi a(n);
for(ll i=0;i<n;++i)
{
cin>>a[i].f>>a[i].s;
a[i].f*=2;
a[i].s*=2;
}
vector<tuple<ll,ll,ll,ll> > b(q);
for(ll i=0;i<q;++i)
{
ll l,r;
cin>>l>>r;
l*=2;
r*=2;
ll mid=(l+r)/2;
b[i]=make_tuple(mid,l,r,i);
}
sortA(b);
sortA(a);
vi ans(q);
new_data_set S;
for(ll i=0,j=0;i<q;++i)
{
ll l=get<1>(b[i]),r=get<2>(b[i]),mid=get<0>(b[i]),ind=get<3>(b[i]);
while(j<n && a[j].f<=mid)
{
S.in({a[j].f-a[j].s,j});
j++;
}
auto it=S.lower_bound({l,-1});
if(it==S.end())
{
ans[ind]+=0;
}
else
{
ans[ind]+=(S.size()-S.ook(*it));
}
}
new_data_set T;
for(ll i=q-1,j=n-1;i>=0;--i)
{
ll l=get<1>(b[i]),r=get<2>(b[i]),mid=get<0>(b[i]),ind=get<3>(b[i]);
while(j>=0 && a[j].f>mid)
{
T.in({a[j].f+a[j].s,j});
j--;
}
auto it=T.upper_bound({r,INF});
if(it==T.end())
{
ans[ind]+=(T.size());
}
else
{
ans[ind]+=(T.ook(*it));
}
}
for(ll i=0;i<q;++i)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
ll t=1;
cin>>t;
while(t--)
{
solve();
}
}