t=int(input())
for i in range(t):
n=int(input())
wall=list(map(int,input().split()))
coord=int(input())
for j in range(coord):
x,y=map(int,input().split())
if x==0 and y==0:
print(0)
elif x+y in wall:
print(-1)
else:
count=0
count=sum(x+y>k for k in wall)
#for k in wall:
#if x+y>k:
#count+=1
print(count)
Can someone help me out ,
Error I am getting is Time Limit Exceed
Obviously you will get TLE, bcz you are running O(n^2) .
Think the walls with the given coordinates as x+y. Now, apply lower_bound on x+y and you will get the number of walls you must break
U searched how many values in array which is less than (x+y) right ? … but u did in O(N) complexity each time , but as in question it is given array is sorted than apply binary search to find count , so that complexity will be O(logN) for each query.
I am very new to coding can you some how show me with comment on the code what should I do?
If i use Binary search instead of linear to with the count of numbers the TLE error will be solved?
You can check my code. I did the same. I have commented my code. Hope it solves your doubt.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define br break
#define pb push_back
#define endl "\n"
#define cc continue
#define ee end
using namespace std;
void solve(){
//input
ll n;
cin>>n;
ll i;
vector<ll>v(n);
map<ll,ll>mp;
for(i=0;i<n;i++){
cin>>v[i];
mp[v[i]]++; //Counting the frequency of the elements
}
sort(v.begin(),v.end());
ll ans=-1;
ll q;
cin>>q;
while(q--){
ll a,b;
cin>>a>>b;
ll x=a+b;
//Since, the points are of the form (a,0),(0,a), so the equation of the line
// is x+y=a, so if a point lies on the line, it must satisfy the equation
if(mp[x]){
cout<<"-1"<<endl;
}
//If source lies on destination
else if(a==0 and b==0){
cout<<0<<endl;
}
else{
// If any of the points is greater than the
//greatest element of the vector, it lies
// outside, so the total walls we have to break is n
if(a>v.back() or b>v.back()){
cout<<n<<endl;
}
//We can find the points that we need to pass by
// lower bound, i.e. it gives the index where it is just ;
//greater than the elements, hence the total walls needed to break
else{
ll z=lower_bound(v.begin(),v.end(),x)-v.begin();
cout<<z<<endl;
}
}
}
}
int32_t main()
{
fio;
ll t=1;
cin>>t;
while(t--){
solve();
}
}
1 Like