Sub1 RE 求调

LiJoQiao @ 2024-09-04 18:46:37

by LiJoQiao @ 2024-09-04 18:46:47

#include<bits/stdc++.h>
using namespace std;
constexpr int MOD1=39989,MOD2=1e9+1,MAXN=1e5+10;
constexpr double eps=1e-9;
int lastans,lcnt;
struct line{
    double k,b;
}ln[MAXN];
int segt[(MOD1+5)<<2]; 
struct Ans{
    int id;double y;
};
#define lid (id<<1)
#define rid ((id<<1)+1)
#define mid ((l+r)>>1)
#define nowid (segt[id])
double calc(int id,int x){//计算x值对应y值
    return ln[id].k*x+ln[id].b; 
}
int cmp(double x,double y){
    if(x-y>eps)return 1;
    else if(y-x>eps)return -1;
    else return 0;
}
void change(int id,int l,int r,int l_id,int ll,int lr){
//  printf("debug:change(%d,%d,%d,%d,%d,%d)\n",id,l,r,l_id,ll,lr);
    if(l>r)return;
    if(ll<=l&&r<=lr){
        if(nowid==0)nowid=l_id;
        else if(cmp(ln[nowid].k,ln[l_id].k)==1){//k_nowid>k_l_id
            if(cmp(calc(l_id,mid),calc(nowid,mid))==1){
                change(rid,mid+1,r,nowid,ll,lr);
                nowid=l_id;
            }else{
                change(lid,l,mid,l_id,ll,lr);
            }
        }else if(cmp(ln[nowid].k,ln[l_id].k)==-1){
            if(cmp(calc(l_id,mid),calc(nowid,mid))==1){
                change(lid,l,mid,nowid,ll,lr);
                nowid=l_id;
            }else{
                change(rid,mid+1,r,l_id,ll,lr);
            }
        }else if(cmp(ln[l_id].b,ln[nowid].b)==1)nowid=l_id;
    }else{
        if(ll<=mid)change(lid,l,mid,l_id,ll,lr);
        if(mid<lr)change(rid,mid+1,r,l_id,ll,lr);
    }
}
Ans query(int id,int l,int r,int loc){
//  printf("debug:query(%d,%d,%d,%d)\n",id,l,r,loc);
//  system("pause");
//  if(loc<l||r<loc/*l>r*/)return {0,-MOD2};
    if(l==r)return {nowid,calc(nowid,loc)};
    Ans cans;
    if(loc<=mid)cans=query(lid,l,mid,loc);
    else cans=query(rid,mid+1,r,loc);
    if(cmp(calc(nowid,loc),cans.y)==1){
        return {nowid,calc(nowid,loc)};
    }else if(cmp(calc(nowid,loc),cans.y)==0){
        if(nowid<cans.id)return {nowid,calc(nowid,loc)};
        else return cans; 
    }else return cans;
}
namespace sol{
    void solve(){
        int n;scanf("%d",&n);
//      ln[segt[0]]={-MOD2,-MOD2};
        while(n--){
            int op;scanf("%d",&op);
            if(!op){
                int k;scanf("%d",&k);
                k=(k+lastans-1)%MOD1+1;
                lastans=query(1,1,MOD1,k).id;
                printf("%d\n",lastans);
            }else{
                int x0_,y0_,x1_,y1_;scanf("%d%d%d%d",&x0_,&y0_,&x1_,&y1_);
                x0_=(x0_+lastans-1)%MOD1+1;y0_=(y0_+lastans-1)%MOD2+1;
                x1_=(x1_+lastans-1)%MOD1+1;y1_=(y1_+lastans-1)%MOD2+1;
                if(x0_>x1_){
                    swap(x0_,x1_);swap(y0_,y1_);
                }
                ++lcnt;
                if(x0_==x1_){ln[lcnt].k=0;ln[lcnt].b=max(y0_,y1_);}
                else{
                    ln[lcnt].k=(double)(y1_-y0_)/(x1_-x0_);
                    //y-y0=k(x-x0)
                    ln[lcnt].b=-ln[lcnt].k*x0_+y0_;
                }
                change(1,1,MOD1,lcnt,x0_,x1_);
            }
        }
    }
}
int main(){
    sol::solve();
    return 0;
}

by Iceturky @ 2024-09-04 18:57:02

歪日，怎么在李超树

太可怕

by lizicheng3042 @ 2024-09-04 19:11:31

经查证，是修改函数递归时边界未判定导致的，在修改操作内加入
if(id>(MOD1<<2))return;
即可 AC

by LiJoQiao @ 2024-09-04 19:43:00

@lizicheng3042 谢谢你。

by LiJoQiao @ 2024-09-04 19:43:20

@Iceturky 我已经调一个周了/fn

by Iceturky @ 2024-09-04 20:18:49

@LiJoQiao 可惜我不会李超树/ll/ll/ll