WA #5,14,16,17 求调

SFlyer @ 2024-03-28 22:50:05

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int M1 = 39989;
const int M2 = 1e9;
const int N = 1e5+5;
const ld eps = 1e-9;

struct line {
    ld k,b;
} p[N];

int cmp(ld x,ld y){
    if (x-y>eps){
        return 1;
    }
    if (y-x>eps){
        return -1;
    }
    return 0;
}

int cnt,s[N<<2];

ld cal(int id,ld x){
    return p[id].k*x+p[id].b;
}

void ins(int x0,int y0,int x1,int y1){
    cnt++;
    if (x0==x1){
        p[cnt].k=0;
        p[cnt].b=max(y0,y1);
    }
    else{
        p[cnt].k=1.*(y1-y0)/(x1-x0);
        p[cnt].b=y0-p[cnt].k*x0;
    }
}

void upd(int rt,int l,int r,int u){
    int &v=s[rt];
    int mid=l+r>>1;
    int bm=cmp(cal(u,mid),cal(v,mid));
    if (bm==1 || (!bm && u<v)){
        swap(u,v);
    }
    int bl=cmp(cal(u,l),cal(v,l));
    int br=cmp(cal(u,r),cal(v,r));
    if (bl==1 || (!bl && u<v)){
        upd(rt<<1,l,mid,u);
    }
    if (br==1 || (!br && u<v)){
        upd(rt<<1|1,mid+1,r,u);
    }
}

void upd(int rt,int cl,int cr,int l,int r,int u){
    if (l==r){

    }
    if (l<=cl && cr<=r){
        upd(rt,cl,cr,u);
        return;
    }
    int mid=cl+cr>>1;
    if (l<=mid){
        upd(rt<<1,cl,mid,l,r,u);
    }
    if (mid<r){
        upd(rt<<1|1,mid+1,cr,l,r,u);
    }
}

pair<int,int> lar(pair<int,int> x,pair<int,int> y){
    int t=cmp(x.first,y.first);
    if (t==-1){
        return y;
    }
    else if (t==1){
        return x;
    }
    return x.second<y.second?x:y; 
}

pair<int,int> qy(int rt,int l,int r,int d){
    if (r<d || d<l){
        return {0,0};
    }
    int mid=l+r>>1;
    ld res=cal(s[rt],d);
    if (l==r){
        return {res,s[rt]};
    }
    return lar({res,s[rt]},lar(qy(rt<<1,l,mid,d),qy(rt<<1|1,mid+1,r,d)));
}

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

    int n,lsta=0;
    cin>>n;
    while (n--){
        int op;
        cin>>op;
        if (op==1){
            int x0,y0,x1,y1;
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+lsta-1+M1)%M1+1;
            x1=(x1+lsta-1+M1)%M1+1;
            y0=(y0+lsta-1+M2)%M2+1;
            y1=(y1+lsta-1+M2)%M2+1;
            if (x0>x1){
                swap(x0,x1);
                swap(y0,y1);
            }
            ins(x0,y0,x1,y1);
            upd(1,1,M1,x0,x1,cnt);
        }
        else{
            int x;
            cin>>x;
            x=(x+lsta-1+M1)%M1+1;
            cout<<(lsta=qy(1,1,M1,x).second)<<"\n";
        }
    }
    return 0;
}
``

by MatrixGroup @ 2024-03-28 23:35:03

卷

by zifanwang @ 2024-03-29 00:08:57

卷

by SFlyer @ 2024-03-29 15:13:24

@SFlyer 现在 Wa #5,#14。

by SFlyer @ 2024-03-29 15:14:36

AC 了。此贴结。

by Fa_Nanf1204 @ 2024-05-21 16:02:44

@SFlyer 我跟你症状一模一样，求大佬帮调（玄关）

#include<bits/stdc++.h>
#define N 100005
#define p2 (p<<1)
#define p3 ((p<<1)|1)
#define mod1 39989
#define mod2 int(1e9)
#define db double 
using namespace std;
const db eps=1e-9;
struct Tree{
    int id;
}tree[(mod1+11)<<2];
struct Line{
    db k,b;
}line[N];
struct Answer{
    db zb;
    int id; 
};
int n,cnt,lastans;
void add(int x,int y,int xx,int yy){ //用一次函数表示线段，便于计算线段在某位置的纵坐标。
    cnt++;
    if(x==xx){
        line[cnt].k=0,line[cnt].b=max(y,yy);
    }
    else{
        line[cnt].k=(db)(yy-y)/(xx-x),line[cnt].b=y-line[cnt].k*x;
    }
}
int cmp(db x,db y){//手写 cmp，避免精度问题
    if(x-y>eps) return 1;
    else if(y-x>eps) return -1;
    return 0;
}
int askzb(int p,int x){
    return line[p].k*x+line[p].b;//计算编号为 p 的线段在 x 处的纵坐标。
}
Answer _max(Answer x,Answer y){
    if(cmp(x.zb,y.zb)==-1){
        return y;
    }
    if(cmp(x.zb,y.zb)==1){
        return x;
    }
    if(x.id<y.id) return x;
    else return y;
}
Answer __max(Answer x,Answer y,Answer z){
    return _max(_max(x,y),z);
}

Answer query(int l,int r,int k,int p){
    if(r<k or k<l) return (Answer){0,0};
    int mid=l+r>>1;
    db ans=askzb(tree[p].id,k);
    if(l==r) return (Answer){ans,tree[p].id};
    return __max((Answer){ans,tree[p].id},query(l,mid,k,p2),query(mid+1,r,k,p3));
}
void modify(int l,int r,int v,int p){
    int &w=tree[p].id,mid=l+r>>1;
    int flag=cmp(askzb(v,mid),askzb(w,mid));
    if(flag==1 or (flag==0 and v<w)) swap(v,w);
    int fl=cmp(askzb(v,l),askzb(w,l)),fr=cmp(askzb(v,r),askzb(w,r));
    if(fl==1 or (fl==0 and v<w)) modify(l,mid,v,p2);
    if(fr==1 or (fr==0 and v<w)) modify(mid+1,r,v,p3);
}
void update(int l,int r,int le,int ri,int v,int p){
    if (l==le and r==ri){
        modify(l,r,v,p);
        return ;
    }
    int mid=l+r>>1;
    if(ri<=mid) update(l,mid,le,ri,v,p2);
    else if (le>mid) update(mid+1,r,le,ri,v,p3);
    else update(l,mid,le,mid,v,p2),update(mid+1,r,mid+1,ri,v,p3);
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        int op,x,y,xx,yy,k;
        cin>>op;
        if(op==0){
            cin>>k;
            k=(k+lastans-1+mod1)%mod1+1;
            //cout<<k<<'\n';
            lastans=query(1,mod1,k,1).id;
            cout<<lastans<<'\n';
        }
        else{
            cin>>x>>y>>xx>>yy;
            x=(x+lastans-1+mod1)%mod1+1;
            xx=(xx+lastans-1+mod1)%mod1+1;
            y=(y+lastans-1+mod2)%mod2+1;
            yy=(yy+lastans-1+mod2)%mod2+1;
            if(x>xx)swap(x,xx),swap(y,yy);
            //cout<<x<<" "<<y<<" "<<xx<<" "<<yy<<'\n';
            add(x,y,xx,yy);
            update(1,mod1,x,xx,cnt,1);
        }
    }
    return 0;
} 

by SFlyer @ 2024-05-21 16:10:39

@Fa_Nanf1204 这个是我帮你 AC 的代码：

// this is test for other's code.
#include<bits/stdc++.h>
#define N 100005
#define p2 (p<<1)
#define p3 ((p<<1)|1)
#define mod1 39989
#define mod2 int(1e9)
#define db long double 
using namespace std;
const db eps=1e-9;
struct Tree{
    int id;
}tree[(mod1+11)<<2];
struct Line{
    db k,b;
}line[N];
struct Answer{
    db zb;
    int id; 
};
int n,cnt,lastans;
void add(int x,int y,int xx,int yy){ //用一次函数表示线段，便于计算线段在某位置的纵坐标。
    cnt++;
    if(x==xx){
        line[cnt].k=0,line[cnt].b=max(y,yy);
    }
    else{
        line[cnt].k=(db)(yy-y)/(xx-x),line[cnt].b=y-line[cnt].k*x;
    }
}
int cmp(db x,db y){//手写 cmp，避免精度问题
    if(x-y>eps) return 1;
    else if(y-x>eps) return -1;
    return 0;
}
db askzb(int p,db x){
    return line[p].k*x+line[p].b;//计算编号为 p 的线段在 x 处的纵坐标。
}
Answer _max(Answer x,Answer y){
    if(cmp(x.zb,y.zb)==-1){
        return y;
    }
    if(cmp(x.zb,y.zb)==1){
        return x;
    }
    if(x.id<y.id) return x;
    else return y;
}
Answer __max(Answer x,Answer y,Answer z){
    return _max(_max(x,y),z);
}

Answer query(int l,int r,int k,int p){
    if(r<k or k<l) return (Answer){0,0};
    int mid=l+r>>1;
    db ans=askzb(tree[p].id,k);
    if(l==r) return (Answer){ans,tree[p].id};
    return __max((Answer){ans,tree[p].id},query(l,mid,k,p2),query(mid+1,r,k,p3));
}
void modify(int l,int r,int v,int p){
    int &w=tree[p].id,mid=l+r>>1;
    int flag=cmp(askzb(v,mid),askzb(w,mid));
    if(flag==1 or (flag==0 and v<w)) swap(v,w);
    int fl=cmp(askzb(v,l),askzb(w,l)),fr=cmp(askzb(v,r),askzb(w,r));
    if(fl==1 or (fl==0 and v<w)) modify(l,mid,v,p2);
    if(fr==1 or (fr==0 and v<w)) modify(mid+1,r,v,p3);
}
void update(int l,int r,int le,int ri,int v,int p){
    if (l==le and r==ri){
        modify(l,r,v,p);
        return ;
    }
    int mid=l+r>>1;
    if(ri<=mid) update(l,mid,le,ri,v,p2);
    else if (le>mid) update(mid+1,r,le,ri,v,p3);
    else update(l,mid,le,mid,v,p2),update(mid+1,r,mid+1,ri,v,p3);
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        int op,x,y,xx,yy,k;
        cin>>op;
        if(op==0){
            cin>>k;
            k=(k+lastans-1+mod1)%mod1+1;
            //cout<<k<<'\n';
            lastans=query(1,mod1,k,1).id;
            cout<<lastans<<'\n';
        }
        else{
            cin>>x>>y>>xx>>yy;
            x=(x+lastans-1+mod1)%mod1+1;
            xx=(xx+lastans-1+mod1)%mod1+1;
            y=(y+lastans-1+mod2)%mod2+1;
            yy=(yy+lastans-1+mod2)%mod2+1;
            if(x>xx)swap(x,xx),swap(y,yy);
            //cout<<x<<" "<<y<<" "<<xx<<" "<<yy<<'\n';
            add(x,y,xx,yy);
            update(1,mod1,x,xx,cnt,1);
        }
    }
    return 0;
} 

应该不用 long double 没事（我就是试一下。）主要的问题是，askzb 函数里面有两处改成 db。

by Fa_Nanf1204 @ 2024-05-21 16:14:43

@SFlyer 感谢大佬，已关