QOJ.ac

QOJ

ID	Submission ID	Problem	Hacker	Owner	Result	Submit time	Judge time
#855	#577718	#9302. Caesar Cipher	ship2077	rotcar07	Success!	2024-09-20 15:14:27	2024-09-20 15:14:27

Details

Extra Test:

Wrong Answer

time: 63ms

memory: 36932kb

input:

458060 114515
0 55427 65535 0 0 53983 65535 0 0 52539 65535 0 0 51095 65535 0 0 49651 65535 0 0 48207 65535 0 0 46763 65535 0 0 45319 65535 0 0 0 65535 10108 0 0 65535 11552 0 0 65535 12996 0 0 65535 14440 0 0 65535 15884 0 0 65535 17328 0 0 65535 18772 0 0 65535 20216 0 62978 65534 0 0 61700 65534 ...

output:

no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
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:

wrong answer expected NO, found YES [109113th token]

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#577718	#9302. Caesar Cipher	rotcar07	WA	457ms	44480kb	C++20	2.1kb	2024-09-20 14:13:37	2024-09-20 15:14:46

answer

//1233 hack me
#include<bits/stdc++.h>
using namespace std;
int n,q;
constexpr int maxn=5e5+5;
int a[maxn];
mt19937 rnd(time(NULL));
typedef unsigned long long ull;
const ull mod=1e9+9,base=rnd()%114514+100000;
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';
    }
}

Source code, Language: C++20