萌新刚学OI！全WA求助

bellmanford @ 2019-08-07 17:15:59

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

#define OPTIMIZE ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define In inline
#define Re register
#define db double
#define ll long long
const int M=1e6+5;
const int n=5e4+5;
const int MOD1=39989;
const int MOD2=1e9;

int q,num=0,lastans=0;
bool vis[M];
struct node{
    int num;
    double b,k;
}x[M<<1],tr[M<<3];

int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*y;
}

double Calc(node hs,int x){
    return 1.0*hs.k*x+hs.b;
}

void insert(int u,int l,int r,int x1,int x2,node p){
    if(l>=x1&&r<=x2){
        int mid=(l+r)>>1;
        if(Calc(tr[u],mid)<Calc(p,mid)||(!tr[u].num)) swap(tr[u],p);
        double jd=1.0*(tr[u].b-p.b)/(p.k-tr[u].k);
        if(l==r||tr[u].k==p.k||jd<1.0*l||jd>1.0*r||(!p.num)) return;
        if(p.k<tr[u].k) insert(u<<1,l,mid,x1,x2,p);
        else insert(u<<1|1,mid+1,r,x1,x2,p);
    }
    else{
        int mid=(l+r)>>1;
        if(x1<=mid) insert(u<<1,l,mid,x1,x2,p);
        if(x2>mid) insert(u<<1|1,mid+1,r,x1,x2,p);
    }
}

node query(int u,int l,int r,int x){
    if(l==r) return tr[u];
    int mid=(l+r)>>1;
    node k;
    if(x<=mid) query(u<<1,l,mid,x);
    else query(u<<1|1,mid+1,r,x);
    return ((!k.num)||Calc(k,x)<Calc(tr[u],x))?tr[u]:k;
}

int main(){
    OPTIMIZE
    freopen("shuju.in","r",stdin);
    q=read();
    while(q--){
        int opt=read();
        if(opt==0){
            int k=read();
            k=(k+lastans-1)%MOD1+1;
            lastans=query(1,1,n,k).num;
            printf("%d\n",lastans);
        }
        if(opt==1){
            int x1=read(),y1=read(),x2=read(),y2=read();
            num++;
            x1=(x1+lastans-1)%MOD1+1;
            y1=(y1+lastans-1)%MOD2+1;
            x2=(x2+lastans-1)%MOD1+1;
            y2=(y2+lastans-1)%MOD2+1;
            if(x1>x2) swap(x1,x2),swap(y1,y2);
            x[num].k=(y1-y2)/(x1-x2);
            x[num].b=(x1*y2-x2*y1)/(x1-x2);
            x[num].num=num;
            insert(1,1,n,x1,x2,x[num]);
        }
    }
}

by zhy137036 @ 2019-08-07 17:21:29

fAKe

by YosemiteHe @ 2019-08-07 17:22:09

@bellmanford 你这还刚学OI？

by 菜鸟k @ 2019-08-07 17:30:13

QNDMX

by bellmanford @ 2019-08-07 18:18:50

@MBAPPE 所以全WA了呀QAQ

by bellmanford @ 2019-08-07 18:37:35

结构体可以交换吗？

by bellmanford @ 2019-08-07 18:58:00

#include <bits/stdc++.h>
#define il inline
#define Max 2000005
#define int long long
#define ll long long
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
#define db double
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
char In[Max],*ss=In,*tt=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    db k,b;
    int id;
}t[Max<<2],s[Max];
il db calc(node a,int x)
{
    //cout<<a.k<<' '<<a.b<<" qwqwq!\n";
    return a.k*x+a.b;
}
il void ins(int x,int l,int r,int ql,int qr,node p)
{
    if(ql<=l&&r<=qr)
    {
        int mid=(l+r)>>1;
        if(calc(t[x],mid)<calc(p,mid)||(!t[x].id)) swap(t[x],p);
        db crs=1.0*(t[x].b-p.b)/(p.k-t[x].k);
        if(l==r||t[x].k==p.k||crs<1.0*l||crs>1.0*r||(!p.id))
        {
            return;
        }
        if(p.k<t[x].k) ins(ls(x),l,mid,ql,qr,p);
        else ins(rs(x),mid+1,r,ql,qr,p);
    }
    int mid=(l+r)>>1;
    if(ql<=mid) ins(ls(x),l,mid,ql,qr,p);
    if(qr>mid) ins(rs(x),mid+1,r,ql,qr,p);
}
il node qry(int x,int l,int r,int p)
{
    if(l==r) return t[x];
    int mid=(l+r)>>1;
    node k;
    if(p<=mid) k=qry(ls(x),l,mid,p);
    else k=qry(rs(x),mid+1,r,p);
    return ((!k.id)||calc(k,p)<calc(t[x],p))?t[x]:k;
}
int q,cnt,opt,ans=0;
char qwq[20];
signed main()
{
    q=read();
    while(q--)
    {
        opt=read();
        if(opt==1)
        {
            ++cnt;
            int x1=read(),y1=read(),x2=read(),y2=read();
            x1=(x1+ans-1)%39989+1;
            x2=(x2+ans-1)%39989+1;
            y1=(y1+ans-1)%1000000001+1;
            y2=(y2+ans-1)%1000000001+1;
            if(x1==x2) continue;
            if(x1>x2) swap(x1,x2),swap(y1,y2);
            s[cnt].k=1.0*(y1-y2)/(x1-x2),s[cnt].b=1.0*y1-1.0*x1*s[cnt].k;
            s[cnt].id=cnt;
            //cout<<cnt<<endl<<' '<<s[cnt].k<<' '<<s[cnt].b<<" qwq!\n";
            //cout<<x1<<' '<<x2<<" qwq\n";
            ins(1,1,40000,x1,x2,s[cnt]);
        }
        if(opt==0)
        {
            int x=read();
            x=(x+ans-1)%39989+1;
            ans=qry(1,1,40000,x).id;
            printf("%lld\n",ans);
        }
    }
}

by bellmanford @ 2019-08-07 18:58:19

这份却可以

by bellmanford @ 2019-08-07 19:40:23

node query(int u,int l,int r,int x){
    if(l==r) return tr[u];
    int mid=(l+r)>>1;
    node k;
    if(x<=mid) query(u<<1,l,mid,x);
    else query(u<<1|1,mid+1,r,x);
    return ((!k.num)||Calc(k,x)<Calc(tr[u],x))?tr[u]:k;
}

by bellmanford @ 2019-08-07 19:40:45

返回错了

by bellmanford @ 2019-08-07 19:41:45

还是WaQAQ