QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427332#7782. Ursa MinormarherWA 1365ms58520kbC++143.5kb2024-06-01 12:46:132024-06-01 12:46:14

Judging History

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

  • [2024-06-01 12:46:14]
  • 评测
  • 测评结果:WA
  • 用时:1365ms
  • 内存:58520kb
  • [2024-06-01 12:46:13]
  • 提交

answer

#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+50,mod=1e9+7,S=500;

mt19937 rad(time(0));

int n,m,q,st[N][20],a[N],b[N],lg[N],x=rad()%mod,fir[N],mi[N],bl[N],imi[N],ix,sum[N],t[S][S+50];

int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        b>>=1;a=a*a%mod;
    }
    return ans;
}

int find(int l,int r)
{
    int k=lg[r-l+1];
    return __gcd(st[l][k],st[r-(1<<k)+1][k]);
}

void ad(int&x,int y)
{
    x+=y;
    x-=x>=mod?mod:0;
}

struct block
{
    int sum[S+50],k,val[S+50];

    void change(int x,int ad)
    {
        sum[bl[x]]=(sum[bl[x]]+ad*mi[x%k]%mod)%mod;
        if(x%k==0)val[bl[x]]=(val[bl[x]]+ad)%mod;
    }

    void init()
    {
        for(int i=1;i<=n;i++)change(i,a[i]);
    }

    int w(int x)
    {
        return a[x]*mi[x%k]%mod;
    }

    int find(int l,int r)
    {
        int ans=0;
        for(int i=l;i<=min(bl[l]*S,r);i++)ad(ans,w(i));
        if(r<=bl[l]*S)return ans;
        for(int i=bl[l]+1;i<bl[r];i++)ad(ans,sum[i]);
        for(int i=r;i>(bl[r]-1)*S;i--)ad(ans,w(i));
        return ans;
    }

    int finds(int l,int r)
    {
        int ans=0;
        for(int i=l;i<=min(bl[l]*S,r);i++)if(i%k==0)ad(ans,w(i));
        if(r<=bl[l]*S)return ans;
        for(int i=bl[l]+1;i<bl[r];i++)ad(ans,val[i]);
        for(int i=r;i>(bl[r]-1)*S;i--)if(i%k==0)ad(ans,w(i));
        return ans;
    }
}B[S+50];

void rebuild(int p)
{
    int l=(p-1)*S+1,r=min(n,p*S);sum[p]=0;
    for(int i=l;i<=r;i++)t[p][i-l+1]=(t[p][i-l]+a[i]*mi[i]%mod)%mod,ad(sum[p],a[i]*mi[i]%mod);
}

int findsum(int l,int r)
{
    int p=bl[l],L=(p-1)*S+1,LL=(bl[r]-1)*S+1;
    if(bl[l]==bl[r])return (t[p][r-L+1]-t[p][l-L]+mod)%mod;
    int ans=0;
    ad(ans,(t[p][S]-t[p][l-L]+mod)%mod);
    ad(ans,t[bl[r]][r-LL+1]);
    for(int i=bl[l]+1;i<bl[r];i++)ad(ans,sum[i]);
    return ans;
}

signed main()
{
    // freopen("root.in","r",stdin);
    // freopen("out.txt","w",stdout);
    cin>>n>>m>>q;lg[0]=-1;mi[0]=fir[0]=imi[0]=1;ix=ksm(x,mod-2);
    for(int i=1;i<=n;i++)cin>>a[i],mi[i]=mi[i-1]*x%mod,fir[i]=(fir[i-1]+mi[i])%mod,imi[i]=imi[i-1]*ix%mod;
    for(int i=1;i<=m;i++)cin>>b[i],st[i][0]=b[i],lg[i]=lg[i>>1]+1;
    for(int i=1;(1<<i)<=m;i++)for(int j=1;j+(1<<i)-1<=m;j++)st[j][i]=__gcd(st[j][i-1],st[j+(1<<i-1)][i-1]);
    for(int i=1;i<=n;i++)bl[i]=(i-1)/S+1;
    for(int i=1;i<=S;i++)B[i].k=i,B[i].init(),rebuild(i);
    int cc=0;
    while(q--)
    {
        char z;cin>>z;
        if(z=='U')
        {
            int pos,x;
            cin>>pos>>x;
            for(int i=1;i<=S;i++)B[i].change(pos,(mod+x-a[pos])%mod);
            a[pos]=x;rebuild(bl[pos]);
            continue;
        }
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        cc++;
        int k=__gcd(r1-l1+1,find(l2,r2));
        // if(cc==1043&&n==2e5)
        // {
        //     cout<<k<<'\n';
        // }
        if(k<=S)
        {
            if(B[k].find(l1,r1)==B[k].finds(l1,r1)*fir[k-1]%mod)puts("Yes");
            else puts("No");
            continue;
        }
        int sa=0,sb=0;
        for(int t=1;(t-1)*k<=n;t++)
        {
            int l=max(l1,(t-1)*k),r=min(r1,t*k-1);
            if(l<=r)
            {
                ad(sa,find(l,r)*imi[(t-1)*k]%mod);
                if(l==(t-1)*k)ad(sb,a[l]);
            }
        }
        if(sa==sb*fir[k-1]%mod)puts("Yes");
        else puts("No");
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 26376kb

input:

6 4 5
1 1 4 5 1 4
3 3 2 4
Q 1 5 1 2
Q 2 5 3 4
U 5 2
Q 1 6 1 2
Q 2 5 3 4

output:

Yes
No
No
Yes

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 26316kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 590ms
memory: 26564kb

input:

2000 2000 200000
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 1 2 0 0 2 2 2 1 0 1 2 1 2 0 0 1 1 1 2 0 0 2 2 2 2 0 2 0 0 2 1 2 0 0 1 2 2 1 0 2 0 0 0 1 2 2 1 2 2 0 0 1 1 1 0 0 2 0 0 1 1 0 2 2 2 1 0 0 1 0 1 2 2 2 1 1 2 2 1 2 1 0 2 2 3 1 3 2 3 1 0 1 2 0 1 1 1 0 2 2 3 2 0 3 2 3 3 1 2 3 1 2 0 1 0 3 1 0 0 2 0 1 2 1 3 2 2...

output:

Yes
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No...

result:

ok 100554 tokens

Test #4:

score: 0
Accepted
time: 455ms
memory: 52344kb

input:

1 200000 200000
998244353
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 100240 tokens

Test #5:

score: 0
Accepted
time: 420ms
memory: 42648kb

input:

6 131072 200000
0 0 0 0 1000000000 1000000000
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

Yes
Yes
Yes
No
No
No
Yes
No
No
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
Yes
No
Yes
N...

result:

ok 100021 tokens

Test #6:

score: -100
Wrong Answer
time: 1365ms
memory: 58520kb

input:

200000 200000 200000
490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
Yes
No
No
No
No
No
No
No
No
N...

result:

wrong answer 1043rd words differ - expected: 'Yes', found: 'No'