QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#853#570779#9302. Caesar Ciphership2077rotcar07Success!2024-09-20 14:19:232024-09-20 14:19:23

Details

Extra Test:

Wrong Answer
time: 3ms
memory: 15856kb

input:

40 1
4 3 1 3 4 1 7 1 1 1 1 3 7 1 7 1 1 6 1 1 1 1 6 1 1 7 1 7 3 1 1 1 1 7 1 4 3 1 3 4
2 1 21 20

output:

yes

result:

wrong answer expected NO, found YES [1st token]

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#570779#9302. Caesar Cipherrotcar07#WA 403ms42312kbC++202.0kb2024-09-17 17:44:232024-10-21 09:31:34

answer

#include<bits/stdc++.h>
using namespace std;
int n,q;
constexpr int maxn=5e5+5;
int a[maxn];
typedef unsigned long long ull;
constexpr ull mod=1e9+9,base=100007;
int mx[maxn<<2],len[maxn<<2];
ull bs[maxn],sb[maxn],hsh[maxn<<2];
#define ls p<<1
#define rs p<<1|1
int g[maxn<<2];
inline void pushup(int p){
    mx[p]=max(mx[ls],mx[rs]);
    hsh[p]=(hsh[ls]*bs[len[rs]]+hsh[rs])%mod;
}
inline void pd(int p,int x){
    mx[p]+=x,g[p]+=x;
    hsh[p]=(hsh[p]+x*sb[len[p]-1])%mod;
}
inline void pushdown(int p){
    if(g[p]){pd(ls,g[p]),pd(rs,g[p]),g[p]=0;}
}
void build(int p,int l,int r){
    len[p]=r-l+1;
    if(l==r) return mx[p]=hsh[p]=a[l],void();
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return pd(p,1);
    int mid=l+r>>1;
    pushdown(p);
    if(ql<=mid) modify(ls,l,mid,ql,qr);
    if(qr>mid) modify(rs,mid+1,r,ql,qr);
    pushup(p);
}
void assign(int p,int l,int r){
    if(mx[p]<65536) return;
    if(l==r){
        mx[p]=hsh[p]=0;
        return;
    }
    int mid=l+r>>1;
    pushdown(p);
    assign(ls,l,mid),assign(rs,mid+1,r);
    pushup(p);
}
ull res;
void query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        res=(res*bs[len[p]]+hsh[p])%mod;
        return;
    }
    int mid=l+r>>1;pushdown(p);
    if(ql<=mid) query(ls,l,mid,ql,qr);
    if(qr>mid) query(rs,mid+1,r,ql,qr);
}
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=bs[0]=sb[0]=1;i<=n;i++) bs[i]=bs[i-1]*base%mod,sb[i]=(sb[i-1]*base+1)%mod;
    build(1,1,n);
    while(q--){
        int op,x,y,z;cin>>op>>x>>y;
        if(op==1) modify(1,1,n,x,y),assign(1,1,n);
        else{
            cin>>z;
            ull A,B;
            res=0;query(1,1,n,x,x+z-1);
            A=res,res=0;query(1,1,n,y,y+z-1);
            B=res;
            puts((A==B)?"yes":"no");
        }
        // cout<<hsh[1]<<'\n';
    }
}