I have solved this problem but not satisfied with time complexity can any please make me understand how can we optimise this solution
Unlock Problem Query
Hey Manoj, can you please share the link of your code so that we can suggest the optimizations in that.
Heyy Manoj !
There can be many solutions to this problem , I am going to describe one of them with segment trees.
you can use the idea of segment trees in which every node stores the maximum value in the range [l,r] . And then you just need to iterate over the given array and check wheather if any element is present in its right side or not that is greater than the current element .
#include
#include
#include<limits.h>
#include
#include
#define ll long long
using namespace std;
class Hostel{
public:
ll a;
ll b;
Hostel(ll a,ll b){
this->a=a;this->b=b;
}
ll dist(){
return aa+bb;
}
};
class HostelCompare{
public:
bool operator()(Hostel a,Hostel b){
return a.dist()>b.dist();
}
};
int main() {
ll t=0,k=0;
ll type=0;
scanf("%lld%lld",&t,&k);
priority_queue<Hostel,vector,HostelCompare > pq;
bool isAnySmall=true;
Hostel emp(INT_MAX,INT_MAX);
Hostel kthsma=emp;
while(t–){
scanf("%lld",&type);
if(type==1){
ll a=0,b=0;
scanf("%lld%lld",&a,&b);
Hostel h(a,b);
if(kthsma.a!=emp.a&&kthsma.b!=emp.b){
if(h.dist()<kthsma.dist()){
isAnySmall=true;
}
}
pq.push(h);
}
if(type==2){
Hostel c=emp;
if(isAnySmall){//if any hostel with less distance as compared to present kth hostel comes, then this loop runs
ll extracted=1;
c=pq.top();
pq.pop();
vector toBeInserted;
toBeInserted.push_back©;
while(extracted!=k&&isAnySmall){
c=pq.top();
extracted++;
toBeInserted.push_back©;
pq.pop();
}
kthsma=c;
for(ll i=0;i<toBeInserted.size()&&isAnySmall;i++){
pq.push(toBeInserted[i]);
}
}
if(!isAnySmall)
cout<<kthsma.dist()<<endl;
else
cout<<c.dist()<<endl;
isAnySmall=false;
}
}
return 0;
}
The above solution got accepted but few test case took more than 3 sec which is quite large. Many coding platform do not allow more than 2 sec for cpp…
Sir, Please help…
I want the solution to this problem(SUBSUMS SPOJ). After watching the tutorial I have some doubts…
- What if the value of n<17. (when there is no need for two vectors for the sum)
Sorry, I got it. No Need to reply I resolved the problem myself.