QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382980 | #7782. Ursa Minor | Graphcity | TL | 2883ms | 379504kb | C++20 | 2.8kb | 2024-04-08 20:39:36 | 2024-04-08 20:39:36 |
Judging History
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...