DRC#4 pA by ub33

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
using namespace std;
const int iris = 1e9+7;

int tp[500010],aa[500010],bb[500010],cc[500010],dd[500010];

struct akari{
    int x,y;
    bool operator<(akari b)const{
        return x*b.y < b.x*y;
    }
};
akari ls[1500010];
int p;

int vigna[5000010];

void mdf(int i,int l,int r,int p,int k)
{
    int m=(l+r)>>1;
    if(l==r)
    {
        vigna[i]=max(vigna[i], k);
        return;
    }
    else if(p<=m)
        mdf(i*2,l,m,p,k);
    else
        mdf(i*2+1,m+1,r,p,k);
    vigna[i]=max(vigna[i*2], vigna[i*2+1]);
}

int qry(int i,int l,int r,int L,int R)
{
    int m=(l+r)>>1;
    if(L<=l && r<=R)
        return vigna[i];
    else if(R<=m)
        return qry(i*2,l,m,L,R);
    else if(L>m)
        return qry(i*2+1,m+1,r,L,R);
    else
        return max(qry(i*2,l,m,L,R),qry(i*2+1,m+1,r,L,R));
}

int sana(int a,int b)
{
    akari qwq={a,b};
    return lower_bound(ls,ls+p,qwq)-ls;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,i,a,b,ans;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>tp[i];
        if(!tp[i])
        {
            cin>>aa[i]>>bb[i];
            ls[p++]={aa[i], bb[i]};
        }
        else
        {
            cin>>aa[i]>>bb[i]>>cc[i]>>dd[i];
            ls[p++]={aa[i], bb[i]};
            ls[p++]={cc[i], dd[i]};
        }
    }
    sort(ls,ls+p);
    for(i=0;i<n;i++)
    {
        if(!tp[i])
        {
            a=aa[i];
            b=bb[i];
            mdf(1,0,p,sana(a,b),a);
        }
        else
        {
            a=sana(aa[i], bb[i]);
            b=sana(cc[i], dd[i]);
            if(a>b)
                swap(a,b);
            ans=qry(1,0,p,a,b);
            if(ans==0)
                ans=-1;
            cout<<ans<<'\n';
        }
    }

    return 0;
}