李超树80pts求调

wa最后两个点,似乎没有发现评测记录跟我一样的

#include<bits/stdc++.h>
using namespace std;
const int mod=39989;
const int MOD=1e9;
int q,lastans,num,a[mod*3][5],tree[mod*12],mx;
double k[mod*3],b[mod*3];
int cmp(double x,double y)
{
    if(x-y>1e-9)
    return 1;
    if(y-x>1e-9)
    return -1;
    return 0;
}
void addline(int x)
{
    if(cmp(a[x][1],a[x][3])==0)
    {
        k[x]=0;
        b[x]=max(a[x][2],a[x][4]);
        return;
    }
    k[x]=double(a[x][4]-a[x][2])/double(a[x][3]-a[x][1]);
    b[x]=double(a[x][2])-double(a[x][1])*k[x];
    return;
}
int lson(int l,int r)
{
    return (l+r)/2;
}
int rson(int l,int r)
{
    return (l+r)/2+1;
}
void get(int l,int r,int x,int to)
{
    if(cmp(to*k[tree[x]]+b[tree[x]],mx)==1)
    {
        mx=to*k[tree[x]]+b[tree[x]];
        lastans=tree[x];
    }
    else if(cmp(to*k[tree[x]]+b[tree[x]],mx)==0)
    {
        lastans=min(lastans,tree[x]);
    }
    if(l==r)
    {
        cout<<lastans<<endl;
        return;
    }
    if(lson(l,r)>=to)
    get(l,lson(l,r),x*2,to);
    else
    get(rson(l,r),r,x*2+1,to);
    return;
}
void change(int l,int r,int x,int l1,int r1)
{
    if(l>=l1&&r<=r1)
    {
        if(cmp(l*k[num]+b[num],l*k[tree[x]]+b[tree[x]])==1&&cmp(r*k[num]+b[num],r*k[tree[x]]+b[tree[x]])==1)
        {
            tree[x]=num;
            return;
        }
        else if(cmp(l*k[num]+b[num],l*k[tree[x]]+b[tree[x]])==0&&cmp(r*k[num]+b[num],r*k[tree[x]]+b[tree[x]])==0)
        {
            tree[x]=min(tree[x],num);
            return;
        }
        double mid=double(r+l)/2.0;
        if(cmp(mid*k[num]+b[num],mid*k[tree[x]]+b[tree[x]])>=0)
        {
            change(l,lson(l,r),x*2,l1,r1);
            change(rson(l,r),r,x*2+1,l1,r1);
            return;
        }
        if(cmp(l*k[num]+b[num],l*k[tree[x]]+b[tree[x]])>=0)
        {
            change(l,lson(l,r),x*2,l1,r1);
        }
        if(cmp(r*k[num]+b[num],r*k[tree[x]]+b[tree[x]])>=0)
        {
            change(rson(l,r),r,x*2+1,l1,r1);
        }
        return;
    }
    if(lson(l,r)>=l1)
    change(l,lson(l,r),x*2,l1,r1);
    if(rson(l,r)<=r1)
    change(rson(l,r),r,x*2+1,l1,r1);
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>q;
    while(q--)
    {
        int op;
        cin>>op;
        if(op==0)
        {
            mx=0;
            int x;
            cin>>x;
            x=(x+lastans-1)%mod+1;
            lastans=0;
            get(1,mod,1,x);
        }
        else
        {
            num++;
            for(int i=1;i<=4;i++)
            {
                cin>>a[num][i];
                if(i%2==1)
                a[num][i]=(a[num][i]+lastans-1+mod)%mod+1;
                else 
                a[num][i]=(a[num][i]+lastans-1+MOD)%MOD+1;
            }
            if(a[num][1]>a[num][3])
            {
                swap(a[num][1],a[num][3]);
                swap(a[num][2],a[num][4]);
            }
            addline(num);
            change(1,mod,1,a[num][1],a[num][3]);
        }
    }
    return 0;
}
//y=kx+b