QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#859740 | #9774. Same Sum | ZZ_zuozhe | WA | 1533ms | 23844kb | C++17 | 2.2kb | 2025-01-17 22:32:04 | 2025-01-17 22:32:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;
int n,q;
int a[N];
int o,t1,t2,t3;
const int mod=998244353;
int ksm(int a,int b=mod-2){
int res=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
return res;
}
const int bs=20050913;
const int ibs=ksm(bs);
inline void ad(int &a,int b){ a=a+b>=mod?a+b-mod:a+b; }
int pw[N];
#define ls x<<1
#define rs x<<1|1
#define mi ((l+r)>>1)
#define lson ls,l,mi
#define rson rs,mi+1,r
ll sum0[N<<2];
int sum1[N<<2],sum2[N<<2];
int lz0[N<<2],lz1[N<<2];
void up(int x){
sum0[x]=sum0[ls]+sum0[rs];
sum1[x]=(sum1[ls]+sum1[rs])%mod;
sum2[x]=(sum2[ls]+sum2[rs])%mod;
}
void tag0(int x,int l,int r,int k){
sum0[x]+=1ll*(r-l+1)*k;
lz0[x]+=k;
}
void tag1(int x,int k){
sum1[x]=1ll*sum1[x]*k%mod;
sum2[x]=1ll*sum2[x]*ksm(k)%mod;
lz1[x]=1ll*lz1[x]*k%mod;
}
void down(int x,int l,int r){
if(lz0[x]){
tag0(ls,l,r,lz0[x]);
tag0(rs,l,r,lz0[x]);
lz0[x]=0;
}
if(lz1[x]!=1){
tag1(ls,lz1[x]);
tag1(rs,lz1[x]);
lz1[x]=1;
}
}
void build(int x,int l,int r){
lz0[x]=0; lz1[x]=1;
if(l==r){
sum0[x]=a[l];
sum1[x]=pw[a[l]];
sum2[x]=ksm(pw[a[l]]);
return;
}
build(lson); build(rson);
up(x);
}
void upd(int x,int l,int r,int nl,int nr,int k){
if(nl<=l&&r<=nr){
tag0(x,l,r,k);
tag1(x,pw[k]);
return;
}
down(x,l,r);
if(mi>=nl)upd(lson,nl,nr,k);
if(mi<nr)upd(rson,nl,nr,k);
up(x);
}
using arr=array<int,3>;
arr operator+(const arr &a,const arr &b){
return {a[0]+b[0],(a[1]+b[1])%mod,(a[2]+b[2])%mod};
}
arr qry(int x,int l,int r,int nl,int nr){
if(nl<=l&&r<=nr)return {sum0[x],sum1[x],sum2[x]};
down(x,l,r);
if(mi<nl)return qry(rson,nl,nr);
if(mi>=nr)return qry(lson,nl,nr);
return qry(lson,nl,nr)+qry(rson,nl,nr);
}
int main(){
pw[0]=1;
for(int i=1;i<N;i++)pw[i]=1ll*pw[i-1]*bs%mod;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
for(int i=1;i<=q;i++){
cin>>o;
if(o==1){
cin>>t1>>t2>>t3;
upd(1,1,n,t1,t2,t3);
}
else{
cin>>t1>>t2;
auto [t,pos,neg]=qry(1,1,n,t1,t2);
if(t%(t2-t1+1>>1)){
puts("NO");
continue;
}
t/=t2-t1+1>>1;
if(1ll*neg*ksm(bs,t)%mod==pos)puts("YES");
else puts("NO");
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 13856kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Wrong Answer
time: 1533ms
memory: 23844kb
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
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 YES, found NO [464th token]