PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Sibasish Ghosh
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Medium
PREREQUISITES:
Segment Trees.
PROBLEM:
The problem basically is :
Store a dynamic list of pairs. You have to answer queries which give you a pair to store in the list and asking you to retrieve a pair having the minimum 2nd value among all the pairs having 2 times the first value of the pair given to store currently.
In case 2 pairs have the minimum 2nd value, return the one having max 1st value then.
QUICK EXPLANATION:
Make a segment tree over a 1-D table of multisets. Make range queries over the table and retrieve the smallest values stored in that range of multisets.
EXPLANATION:
This is a kind of medium-level implementation question requiring you to use a segment tree(also possible in fenwick tree) to get the desired value.
Make a N sized array of multisets where ith element will represent the multiset storing the price of the phones having performance equal to i.
Building a segment tree over this array will allow us to make queries over a range [L,R] to get the cheapest phone having performance in the range [L,R]. The segment tree should be made of pairs to store the location of the minimum value too incase 2 phones of different performance have the same cheapest price.
Total time complexity is in the order O(NlogN+Mlog(N+M)).
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
const int inf=1e9;
multiset<int> mst[N];
pair<int,int> t[4*N];
pair<int,int> neg={-1,-1};
pair<int,int> compareit(pair<int,int> p1,pair<int,int> p2)
{
if(p1!=neg&&p2!=neg)
{
if(p1.first==p2.first)
return p2;
else return min(p1,p2);
}
else if(p1!=neg||p2!=neg)
{
if(p1==neg)
return p2;
else return p1;
}
else return neg;
}
void build(int v,int tl,int tr)
{
if(tl==tr)
{
if(mst[tl].size()==0)
t[v]=neg;
else t[v]= {*mst[tl].begin(),tl};
}
else {
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
pair<int,int> p1=t[v*2],p2=t[v*2+1];
t[v]=compareit(p1,p2);
}
}
pair<int,int> query(int v,int tl,int tr,int l,int r)
{
if(l>r)return neg;
if(l==tl&&r==tr)
{
return t[v];
}
else {
int tm=(tl+tr)/2;
pair<int,int> p1,p2;
p1=query(v*2,tl,tm,l,min(tm,r));
p2=query(v*2+1,tm+1,tr,max(l,tm+1),tr);
return compareit(p1,p2);
}
}
void modify(int v,int tl,int tr,int pos,int val,int type)
{
if(tl==tr)
{
if(type){
mst[tl].insert(val);
}
else{
mst[tl].erase(mst[tl].find(val));
}
if(mst[tl].size()==0)
t[v]=neg;
else t[v]= {*mst[tl].begin(),tl};
}
else {
int tm=(tl+tr)/2;
if(pos<=tm) modify(v*2,tl,tm,pos,val,type);
else modify(v*2+1,tm+1,tr,pos,val,type);
pair<int,int> p1=t[v*2],p2=t[v*2+1];
t[v]=compareit(p1,p2);
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
// #ifdef Zoro
// freopen("/home/pritish/Competitive/in", "r", stdin);
// freopen("/home/pritish/Competitive/out", "w", stdout);
// #endif
int n,m;
cin>>n;
build(1,0,N);
for(int i=0;i<n;i++)
{
int p,s;
cin>>p>>s;
modify(1,0,N,s,p,1);
}
cin>>m;
while(m--)
{
int p,s;
cin>>p>>s;
modify(1,0,N,s,p,1);
pair<int,int> ans=query(1,0,N,s*2,N);
if(ans.first==-1)
cout<<-1<<'\n';
else{
cout<<ans.first<<" "<<ans.second<<'\n';
modify(1,0,N,ans.second,ans.first,0);
}
}
cerr<<"SegTree:\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
const int inf=1e9;
multiset<int> mst[N];
pair<int,int> t[4*N];
pair<int,int> neg={-1,-1};
pair<int,int> compareit(pair<int,int> p1,pair<int,int> p2)
{
if(p1!=neg&&p2!=neg)
{
if(p1.first==p2.first)
return p2;
else return min(p1,p2);
}
else if(p1!=neg||p2!=neg)
{
if(p1==neg)
return p2;
else return p1;
}
else return neg;
}
void build(int v,int tl,int tr)
{
if(tl==tr)
{
if(mst[tl].size()==0)
t[v]=neg;
else t[v]= {*mst[tl].begin(),tl};
}
else {
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
pair<int,int> p1=t[v*2],p2=t[v*2+1];
t[v]=compareit(p1,p2);
}
}
pair<int,int> query(int v,int tl,int tr,int l,int r)
{
if(l>r)return neg;
if(l==tl&&r==tr)
{
return t[v];
}
else {
int tm=(tl+tr)/2;
pair<int,int> p1,p2;
p1=query(v*2,tl,tm,l,min(tm,r));
p2=query(v*2+1,tm+1,tr,max(l,tm+1),tr);
return compareit(p1,p2);
}
}
void modify(int v,int tl,int tr,int pos,int val,int type)
{
if(tl==tr)
{
if(type){
mst[tl].insert(val);
}
else{
mst[tl].erase(mst[tl].find(val));
}
if(mst[tl].size()==0)
t[v]=neg;
else t[v]= {*mst[tl].begin(),tl};
}
else {
int tm=(tl+tr)/2;
if(pos<=tm) modify(v*2,tl,tm,pos,val,type);
else modify(v*2+1,tm+1,tr,pos,val,type);
pair<int,int> p1=t[v*2],p2=t[v*2+1];
t[v]=compareit(p1,p2);
}
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
// #ifdef Zoro
// freopen("/home/pritish/Competitive/in", "r", stdin);
// freopen("/home/pritish/Competitive/out", "w", stdout);
// #endif
int n,m;
cin>>n;
build(1,0,N);
for(int i=0;i<n;i++)
{
int p,s;
cin>>p>>s;
modify(1,0,N,s,p,1);
}
cin>>m;
while(m--)
{
int p,s;
cin>>p>>s;
modify(1,0,N,s,p,1);
pair<int,int> ans=query(1,0,N,s*2,N);
if(ans.first==-1)
cout<<-1<<'\n';
else{
cout<<ans.first<<" "<<ans.second<<'\n';
modify(1,0,N,ans.second,ans.first,0);
}
}
cerr<<"SegTree:\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}