$O(n\ log_2 n)$ but 1e6也过不去

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
ll gcd(ll x,ll y)
{
	return y==0?x:gcd(y,x%y);
}
struct fraction{
	int a=0,b=1;
	void simplify(){
		if(a==0)
		{
			b=1;
			return;
		}
		int t=gcd(a,b);
		a/=t,b/=t;
	}
	fraction(int x,int y)
	{
		a=x,b=y;
		if(b==0)b=1;
//		simplify();
	}
	fraction(int x)
	{
		a=x;
	}
	fraction(){a=0,b=1;}
};
bool operator<(fraction x,fraction y)
{
	long long tb=1ll*x.b/gcd(x.b,y.b)*y.b;
	long long xa=1ll*x.a*tb/x.b , ya=1ll*y.a*tb/y.b;
	return xa<ya;
}
bool operator>(fraction x,fraction y)
{
	long long tb=1ll*x.b/gcd(x.b,y.b)*y.b;
	long long xa=1ll*x.a*tb/x.b , ya=1ll*y.a*tb/y.b;
	return xa>ya;
}
bool operator==(fraction x,fraction y)
{
	x.simplify(),y.simplify();
	return x.a==y.a&&x.b==y.b;
}
int a[N],b[N],c[N];
fraction ans[N];//fst:ai,sec:bi
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	priority_queue<fraction,vector<fraction>,greater<fraction> > q;
	int n,Q;
	cin>>n>>Q;
	map<pair<int,int>,bool> vis;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;++i)
	{
		cin>>b[i];
	}
	int maxc=-1;
	for(int i=1;i<=Q;++i)
	{
		cin>>c[i];
		maxc=max(maxc,c[i]);
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1,greater<int>());
	int x=1,y=1;
	for(int i=1;i<=n;++i){
		q.push(fraction(a[1],b[i]));
		vis[make_pair(1,i)]=1;
	}
	for(int i=2;i<=n;++i){
		q.push(fraction(a[i],b[1]));
		vis[make_pair(i,1)]=1;
	}
	for(int i=1;i<=maxc;++i)
	{
		fraction t=q.top();
		q.pop();
		x=lower_bound(a+1,a+n+1,t.a)-a,y=lower_bound(b+1,b+n+1,t.b,greater<int>())-b;
		if(x+1<=n&&!vis[make_pair(x+1,y)])q.push(fraction(a[x+1],b[y])),vis[make_pair(x+1,y)]=1;
		if(y+1<=n&&!vis[make_pair(x,y+1)])q.push(fraction(a[x],b[y+1])),vis[make_pair(x,y+1)]=1;
		t.simplify();
		ans[i]=t;
	}
	for(int i=1;i<=Q;++i)
	{
		cout<<ans[c[i]].a<<' '<<ans[c[i]].b<<endl;
	}
	return 0;
}