QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#382980#7782. Ursa MinorGraphcityTL 2883ms379504kbC++202.8kb2024-04-08 20:39:362024-04-08 20:39:36

Judging History

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

  • [2024-04-08 20:39:36]
  • 评测
  • 测评结果:TL
  • 用时:2883ms
  • 内存:379504kb
  • [2024-04-08 20:39:36]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5+2,B=448;
const int base=19260817,Mod=1e9+7;

inline int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%Mod;
        x=1ll*x*x%Mod,y>>=1;
    }
    return res;
}

int n,m,q,a[Maxn+5],b[Maxn+5],st[Maxn+5][20],pw[Maxn+5];
int L[Maxn+5],R[Maxn+5],idx[Maxn+5],iv[Maxn+5],tot;
inline int Get(int l,int r)
{int len=__lg(r-l+1); return __gcd(st[l][len],st[r-(1<<len)+1][len]);}

struct Block
{
    int sum[B+5],a[Maxn+5];
    inline void Upd(int x,int y)
    {sum[idx[x]]=(1ll*sum[idx[x]]-a[x]+y+Mod)%Mod,a[x]=y;}
    inline int Count(int x)
    {
        if(x==0) return 0;
        int res=0; For(i,1,idx[x]-1) res=(res+sum[i])%Mod;
        For(i,L[idx[x]],x) res=(res+a[i])%Mod; return res;
    }
} T[B+2];

struct Fenwick
{
    int sum[Maxn+5],pr[Maxn+5],a[Maxn+5];
    inline void Upd(int x,int y)
    {
        int dlt=(y-a[x]+Mod)%Mod; a[x]=y;
        For(i,x,R[idx[x]]) pr[i]=(pr[i]+dlt)%Mod;
        For(i,idx[x],tot) sum[i]=(sum[i]+dlt)%Mod;
    }
    inline int Count(int x) {return x==0?0:(sum[idx[x]-1]+pr[x])%Mod;}
} F1,F2;

int main()
{
    // freopen("1.in","r",stdin);

    cin>>n>>m>>q; For(i,1,n) cin>>a[i];
    pw[0]=1; For(i,1,Maxn) pw[i]=1ll*pw[i-1]*base%Mod;
    iv[0]=1; For(i,1,Maxn) iv[i]=Pow(pw[i],Mod-2);
    For(i,1,m) cin>>b[i],st[i][0]=b[i];
    For(j,1,19) for(int i=1;i+(1<<j)-1<=m;++i)
        st[i][j]=__gcd(st[i][j-1],st[i+(1<<j-1)][j-1]);
    for(int i=1;i<=n;i+=B) L[++tot]=i,R[tot]=min(n,i+B-1);
    For(i,1,tot) For(j,L[i],R[i]) idx[j]=i;
    For(i,1,n) For(j,1,B) T[j].Upd(i,1ll*a[i]*pw[i%j]%Mod);
    For(i,1,n) F1.Upd(i,a[i]),F2.Upd(i,1ll*a[i]*pw[i]%Mod);
    int it=0; while(q--)
    {
        char ch; int l,r,x,y; cin>>ch;
        if(ch=='U')
        {
            cin>>x>>y;
            For(i,1,B) T[i].Upd(x,1ll*y*pw[x%i]%Mod);
            F1.Upd(x,y),F2.Upd(x,1ll*y*pw[x]%Mod);
        }
        if(ch=='Q')
        {
            cin>>l>>r>>x>>y; int k=__gcd(Get(x,y),r-l+1);
            int sum=(F1.Count(r)-F1.Count(l-1)+Mod)%Mod;
            sum=1ll*sum*Pow(k,Mod-2)%Mod;
            sum=1ll*sum*(pw[k]-1)%Mod*Pow(base-1,Mod-2)%Mod;
            int all=0;
            if(k<=B) all=(T[k].Count(r)-T[k].Count(l-1)+Mod)%Mod;
            else
            {
                For(i,0,n/k)
                {
                    int a=i*k,b=(i+1)*k-1; a=max(a,l),b=min(b,r);
                    if(a<=b)
                    {
                        int now=(F2.Count(b)-F2.Count(a-1)+Mod)%Mod;
                        all=(all+1ll*now*iv[i*k]%Mod)%Mod;
                    }
                }
            }
            puts(sum==all?"Yes":"No");
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 25ms
memory: 14504kb

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: 28ms
memory: 14380kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 696ms
memory: 17976kb

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: 396ms
memory: 27448kb

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: 352ms
memory: 24620kb

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: 0
Accepted
time: 2075ms
memory: 379400kb

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:

ok 187340 tokens

Test #7:

score: 0
Accepted
time: 1898ms
memory: 379388kb

input:

200000 200000 200000
360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531...

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 199985 tokens

Test #8:

score: 0
Accepted
time: 1857ms
memory: 379408kb

input:

200000 200000 200000
793134805 922104801 158394038 993313213 77527653 992889267 148461787 499165677 132176015 189185554 783374975 332147281 923925325 371040161 393285793 437388761 138662855 212488140 265392646 498903298 578518594 550390771 960084339 408548934 56106823 814997309 456913457 300689692 1...

output:

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
No
No
No
No
No
No
No
No
No
No
No
No
Yes
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
No
No
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...

result:

ok 200000 tokens

Test #9:

score: 0
Accepted
time: 1838ms
memory: 379396kb

input:

200000 200000 200000
451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037 451942036 451942035 451942037...

output:

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

result:

ok 199977 tokens

Test #10:

score: 0
Accepted
time: 1925ms
memory: 379504kb

input:

200000 200000 200000
606894463 710609424 913364361 30426550 801940265 516097169 349718376 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606894463 710609424 913364361 30426550 801940265 516097169 349718376 606...

output:

No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
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
Yes
No
No
No
No
No
No
N...

result:

ok 100329 tokens

Test #11:

score: 0
Accepted
time: 2824ms
memory: 379192kb

input:

200000 199999 200000
903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886 903745886...

output:

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

result:

ok 100000 tokens

Test #12:

score: 0
Accepted
time: 2883ms
memory: 379436kb

input:

199997 199989 199999
516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047 516381047...

output:

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

result:

ok 100000 tokens

Test #13:

score: -100
Time Limit Exceeded

input:

200000 199899 200000
738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100 738568100...

output:

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

result: