QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611845#9242. An Easy Geometry Problemcrush_codemakerWA 3ms24732kbC++144.8kb2024-10-04 23:13:182024-10-04 23:13:18

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 23:13:18]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:24732kb
  • [2024-10-04 23:13:18]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define N 200007
#pragma GCC optimize(2)
using namespace std;
int n,q,k,b;
int A[N];
struct Node
{
    int h1,h2,sz;
    bool operator == (const Node &other) const
    {
        return h1==other.h1&&h2==other.h2&&sz==other.sz;
    }
};
struct segment_tree
{

    Node tr[N<<2];
    int tg[N<<2];
    int cf1[N],cf2[N];
    int ta1[N],ta2[N];
    int b1=100007,b2=99997;
    int p1=998244353,p2=1e9+7;
    Node mge(Node x,Node y)
    {
        return {(y.h1+(x.h1*cf1[y.sz])%p1)%p1,(y.h2+(x.h2*cf2[y.sz])%p2)%p2,x.sz+y.sz};
    }
    void pu(int i)
    {
        tr[i]=mge(tr[i<<1],tr[i<<1|1]);
    }
    void pd(int i,int l,int r)
    {
        if(!tg[i])
        {
            return ;
        }
        int mid=(l+r)>>1;
        tg[i<<1]+=tg[i];
        tg[i<<1|1]+=tg[i];
        tr[i<<1].h1=(tr[i<<1].h1+((tg[i]%p1)*ta1[mid-l+1])%p1)%p1;
        tr[i<<1].h2=(tr[i<<1].h2+((tg[i]%p2)*ta2[mid-l+1])%p2)%p2;
        tr[i<<1|1].h1=(tr[i<<1|1].h1+((tg[i]%p1)*ta1[r-mid])%p1)%p1;
        tr[i<<1|1].h2=(tr[i<<1|1].h2+((tg[i]%p2)*ta2[r-mid])%p2)%p2;
        tg[i]=0;
    }
    void bd(int i,int l,int r)
    {
        if(l==r)
        {
            tr[i].h1=tr[i].h2=0;
            tr[i].sz=r-l+1;
            tg[i]=0;
        }
        else
        {
            int mid=(l+r)>>1;
            bd(i<<1,l,mid);
            bd(i<<1|1,mid+1,r);
            tr[i].h1=tr[i].h2=0;
            tr[i].sz=r-l+1;
            tg[i]=0;
        }
    }
    void up(int x,int L,int R,int i,int l,int r)
    {
        if(L<=l&&r<=R)
        {
            tg[i]+=x;
            tr[i].h1=(tr[i].h1+((x%p1)*ta1[r-l+1])%p1)%p1;
            tr[i].h2=(tr[i].h2+((x%p2)*ta2[r-l+1])%p2)%p2;
        }
        else
        {
            int mid=(l+r)>>1;
            pd(i,l,r);
            if(L<=mid)
            {
                up(x,L,R,i<<1,l,mid);
            }
            if(R>mid)
            {
                up(x,L,R,i<<1|1,mid+1,r);
            }
            pu(i);
        }
    }
    Node qq(int L,int R,int i,int l,int r)
    {
        if(L<=l&&r<=R)
        {
            return tr[i];
        }
        else
        {
            int mid=(l+r)>>1;
            pd(i,l,r);
            if(L<=mid&&R>mid)
            {
                return mge(qq(L,R,i<<1,l,mid),qq(L,R,i<<1|1,mid+1,r));
            }
            else if(L<=mid&&!(R>mid))
            {
                return qq(L,R,i<<1,l,mid);
            }
            else if(!(L<=mid)&&R>mid)
            {
                return qq(L,R,i<<1|1,mid+1,r);
            }
            else
            {
                return {0,0,0};
            }
        }
    }
    void init()
    {
        bd(1,1,n);
        cf1[0]=1;
        for(int i=1;i<=n;i++)
        {
            cf1[i]=(cf1[i-1]*b1)%p1;
        }
        cf2[0]=1;
        for(int i=1;i<=n;i++)
        {
            cf2[i]=(cf2[i-1]*b2)%p2;
        }
        ta1[0]=0;
        for(int i=1;i<=n;i++)
        {
            ta1[i]=(1+(ta1[i-1]*b1)%p1)%p1;
        }
        ta2[0]=0;
        for(int i=1;i<=n;i++)
        {
            ta2[i]=(1+(ta2[i-1]*b2)%p2)%p2;
        }
    }
    void upd(int x,int L,int R)
    {
        up(x,L,R,1,1,n);
    }
    Node qur(int L,int R)
    {
        return qq(L,R,1,1,n);
    }
};
struct DS
{
    segment_tree st1,st2;
    void init()
    {
        st1.init();
        st2.init();
        for(int i=1;i<=n;i++)
        {
            st1.upd(2*A[i]-k*i-2*b+(int)(1e10),i,i);
            st2.upd(2*A[i]-k*i+(int)(1e10),n+1-i,n+1-i);
        }
    }
    void upd(int x,int L,int R)
    {
        st1.upd(2*x,L,R);
        st2.upd(2*x,n+1-R,n+1-L);
    }
    int check(int x,int y)
    {
        if(y==0)
        {
            return 1;
        }
        return st1.qur(x+1,x+y)==st2.qur(n+1-(x-1),n+1-(x-y));
    }
    int qur(int x)
    {
        int l=0,r=min(n-x,x-1);
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(check(x,mid))
            {
                l=mid;
            }
            else
            {
                r=mid-1;
            }
        }
        int ans=l;
        return ans;
    }
};
DS ds;
void solve()
{
    //scanf("%lld%lld%lld%lld",&n,&q,&k,&b);
    n=5000;q=5000;k=2;b=0;
    for(int i=1;i<=n;i++)
    {
        //scanf("%lld",&A[i]);
        A[i]=i+792;
    }
    ds.init();
    while(q--)
    {
        int op;
        scanf("%lld",&op);
        if(op==1)
        {
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            ds.upd(x,l,r);
        }
        else if(op==2)
        {
            int x;
            scanf("%lld",&x);
            int ans=ds.qur(x);
            printf("%lld\n",ans);
        }
    }
}
signed main()
{
    solve();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 24732kb

input:

6 6 6 2
1 5 9 10 15 18
2 2
1 3 3 -3
2 2
1 3 4 3
2 3
2 4

output:

0
1
0
0
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
...

result:

wrong answer 1st numbers differ - expected: '1', found: '0'