QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#287105#7782. Ursa Minorbachbeo2007TL 114ms54796kbC++235.2kb2023-12-19 16:36:322023-12-19 16:36:33

Judging History

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

  • [2023-12-19 16:36:33]
  • 评测
  • 测评结果:TL
  • 用时:114ms
  • 内存:54796kb
  • [2023-12-19 16:36:32]
  • 提交

answer

// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=200005;
const int bl=450;
const int maxs=455;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;

int n,m,q,a[maxn];

int g[maxn][maxl],lg2[maxn];
int query(int l,int r){
    int p=lg2[r-l+1];
    return __gcd(g[l][p],g[r-(1<<p)+1][p]);
}
void build_sparse(){
    for(int i=2;i<=m;i++) lg2[i]=lg2[i/2]+1;
    for(int i=1;i<18;i++){
        for(int j=1;j<=(m-(1<<i)+1);j++) g[j][i]=__gcd(g[j][i-1],g[j+(1<<(i-1))][i-1]);
    }
}

struct Query{
    int id,x,y;
}qq[maxn];
int pw[maxn],inv[maxn];
bool check[maxn],res[maxn];

struct SQRT{
    int cur[maxn],total[maxs];
    void update(int x,int val){
        total[x/bl]=(total[x/bl]-cur[x]+mod)%mod;
        cur[x]=val;
        total[x/bl]=(total[x/bl]+cur[x])%mod;
    }
    int query(int l,int r){
        int sum=0;
        for(int i=l;i<=r;i++){
            if(i%bl==0 && i+bl-1<=r){
                sum=(sum+total[i/bl])%mod;
                i+=bl-1;
            }
            else sum=(sum+cur[i])%mod;
        }
        return sum;
    }
}f0,fall;

struct SQRT2{
    int pre[maxn],lazy[maxs];
    void build(){
        for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+a[i]*pw[i])%mod;
    }
    void update(int x,int val){
        int d=(val-a[x]+mod)*pw[x]%mod;
        a[x]=val;
        for(int i=x;i<=n;i++){
            if(i%bl==0){
                lazy[i/bl]=(lazy[i/bl]+d)%mod;
                i+=bl-1;
            }
            else pre[i]=(pre[i]+d)%mod;
        }
    }
    int query(int l,int r){
        l--;
        int total=(pre[r]+lazy[r/bl]-pre[l]-lazy[l/bl])%mod;
        total=(total+mod)%mod;
        return total;
    }
}f1;

void solve(){
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> g[i][0];
    build_sparse();
    pw[0]=inv[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*base%mod;
        inv[i]=power(inv[i],mod-2)%mod;
    }
    for(int i=1;i<=q;i++){
        char c;cin >> c;
        if(c=='Q'){
            int l,r,s,t;cin >> l >> r >> s >> t;
            int d=__gcd(r-l+1,query(s,t));
            qq[i]={d,l,r};
            check[d]=true;
        }
        else{
            int p,v;cin >> p >> v;
            qq[i]={-1,p,v};
        }
    }
    for(int k=1;k<=bl;k++){
        if(!check[k]) continue;
        for(int i=1;i<=n;i++){
            fall.update(i,a[i]*pw[i%k]%mod);
            if(i%k==0) f0.update(i/k,a[i]);
        }
        for(int i=1;i<=q;i++){
            if(qq[i].id!=-1 && qq[i].id!=k) continue;
            if(qq[i].id==-1){
                int x=qq[i].x,val=qq[i].y;
                fall.update(x,val*pw[x%k]%mod);
                if(x%k==0) f0.update(x/k,val);
            }
            else{
                int l=qq[i].x,r=qq[i].y;
                int total=fall.query(l,r);
                l=(l-1)/k+1;r/=k;
                int S=f0.query(l,r)*(pw[k]+mod-1)%mod*power(base-1,mod-2)%mod;
                res[i]=(S==total);
            }
        }
    }

    for(int i=1;i<=n;i++) f1.build();
    for(int i=1;i<=q;i++){
        if(qq[i].id!=-1 && qq[i].id<=bl) continue;
        if(qq[i].id==-1){
            int x=qq[i].x,val=qq[i].y;
            f1.update(x,val);
        }
        else{
            int l=qq[i].x,r=qq[i].y,k=qq[i].id;
            int total=0,S=0;
            while(l<=r){
                total=(total+f1.query(l,l+k-1)*inv[l]%mod)%mod;
                S=(S+a[l])%mod;l+=k;
            }
            S=S*(pw[k]+mod-1)%mod*power(base-1,mod-2)%mod;
            res[i]=(S==total);
        }
    }

    for(int i=1;i<=q;i++){
        if(qq[i].id!=-1) cout << (res[i]?"Yes":"No") << '\n';
    }

}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 13980kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 114ms
memory: 16880kb

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: 75ms
memory: 54796kb

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: 59ms
memory: 42364kb

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
Time Limit Exceeded

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:


result: