QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#851 | #577704 | #9302. Caesar Cipher | ship2077 | rotcar07 | Success! | 2024-09-20 14:15:43 | 2024-09-20 14:15:44 |
詳細信息
Extra Test:
Wrong Answer
time: 3ms
memory: 15912kb
input:
80 2 9 3 1 1 1 6 1 1 1 1 1 1 9 8 1 7 5 4 1 1 1 1 4 5 7 1 8 9 1 1 1 1 1 1 6 1 1 1 3 9 5 3 1 1 1 10 9 1 1 1 1 1 5 1 1 5 7 8 1 1 1 1 8 7 5 1 1 5 1 1 1 1 1 9 10 1 1 1 3 5 2 1 21 20 2 41 61 20
output:
no yes
result:
wrong answer expected NO, found YES [2nd token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#577704 | #9302. Caesar Cipher | rotcar07 | WA | 525ms | 44344kb | C++20 | 2.0kb | 2024-09-20 14:11:33 | 2024-09-20 14:16:02 |
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+5,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';
}
}