QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1300 | #826993 | #9774. Same Sum | ship2077 | huaxiamengjin | Success! | 2024-12-23 09:41:05 | 2024-12-23 09:41:05 |
詳細信息
Extra Test:
Wrong Answer
time: 0ms
memory: 16012kb
input:
92 1 0 27835 7771 100000 0 39328 43596 100000 0 45543 1804 100000 0 15065 33189 100000 0 34865 33086 100000 0 31953 49149 100000 0 14280 22015 100000 0 19244 49807 100000 0 35097 26681 100000 0 971 2303 100000 0 32040 17625 100000 0 8393 23792 100000 0 9022 30450 100000 0 34572 13986 100000 0 8393 2...
output:
Yes
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#826993 | #9774. Same Sum | huaxiamengjin | WA | 1660ms | 16748kb | C++14 | 3.2kb | 2024-12-22 18:13:15 | 2024-12-23 09:46:26 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NN=998244353;
int mi(int x,int y){
int sum=1;
for (;y;y>>=1,x=x*x%NN)
if(y&1)sum=sum*x%NN;
return sum;
}
int len=300;
const int bs=1233;
int a[200200],b[200200],c[200200];
int tag[200200],s1[200200],s2[200200];
int mn[200200],mx[200200],col[200200];
int ls[200200],rs[200200];
int n,q;
const int bss=mi(bs,NN-2);
void push(int p,int l,int r,int v){
// cout<<p<<" "<<l<<" "<<r<<" "<<v<<"\n";
int ll=ls[p],rr=rs[p];
int tmp=mi(bs,tag[p]);
for (int i=ll;i<=rr;i++)a[i]=a[i]*tmp%NN;
tmp=mi(bs,v);
for (int i=l;i<=r;i++)a[i]=a[i]*tmp%NN;
s1[p]=0;
for (int i=ll;i<=rr;i++)s1[p]=(s1[p]+a[i])%NN;
tmp=mi(bss,tag[p]);
for (int i=ll;i<=rr;i++)b[i]=b[i]*tmp%NN;
tmp=mi(bss,v);
for (int i=l;i<=r;i++)b[i]=b[i]*tmp%NN;
s2[p]=0;
for (int i=ll;i<=rr;i++)s2[p]=(s2[p]+b[i])%NN;
for (int i=ll;i<=rr;i++)
c[i]+=tag[p];
for (int i=l;i<=r;i++)
c[i]+=v;
// cout<<c[l]<<"~~~~~~~\n";
mn[p]=1e15,mx[p]=0;
for (int i=ll;i<=rr;i++)
mn[p]=min(mn[p],c[i]),mx[p]=max(mx[p],c[i]);
tag[p]=0;
}
int ss1,ss2,mxx,mnn;
void get(int p,int l,int r){
int ll=ls[p],rr=rs[p];
int tmp=mi(bs,tag[p]);
for (int i=ll;i<=rr;i++)a[i]=a[i]*tmp%NN;
tmp=mi(bss,tag[p]);
for (int i=ll;i<=rr;i++)b[i]=b[i]*tmp%NN;
for (int i=ll;i<=rr;i++)c[i]+=tag[p];
for(int i=l;i<=r;i++)
ss1=(ss1+a[i])%NN,ss2=(ss2+b[i])%NN;
for (int i=l;i<=r;i++)
mxx=max(mxx,c[i]),mnn=min(mnn,c[i]);
tag[p]=0;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for (int i=1,x;i<=n;i++)
cin>>x,a[i]=mi(bs,x),b[i]=mi(bss,x),c[i]=x;
int tot=0;
for (int l=1;;l+=len){
int r=min(n,l+len-1);
tot++;ls[tot]=l;rs[tot]=r;
mn[tot]=1e15,mx[tot]=0;
for (int i=l;i<=r;i++)
col[i]=tot,s1[tot]=(s1[tot]+a[i])%NN
,s2[tot]=(s2[tot]+b[i])%NN,
mn[tot]=min(mn[tot],c[i]),
mx[tot]=max(mx[tot],c[i]);
if(r==n)break;
}
int op,l,r,v;
while(q--){
cin>>op;
if(op==1){
cin>>l>>r>>v;
int ll=col[l],rr=col[r];
if(ll==rr){
push(ll,l,r,v);
continue;
}
push(ll,l,rs[ll],v);
push(rr,ls[rr],r,v);
int tmp=mi(bs,v),tmp2=mi(bss,v);
for (int i=ll+1;i<rr;i++)
tag[i]+=v,s1[i]=s1[i]*tmp%NN,s2[i]=s2[i]*tmp2%NN
,mn[i]+=v,mx[i]+=v;
}else{
cin>>l>>r;
int ll=col[l],rr=col[r];
ss1=0,ss2=0;mnn=1e15,mxx=0;
if(ll==rr){
get(ll,l,r);
if(ss2*mi(bs,mxx+mnn)%NN==ss1)cout<<"Yes\n";
else cout<<"No\n";
continue;
}
get(ll,l,rs[ll]);
get(rr,ls[rr],r);
for (int i=ll+1;i<rr;i++)
ss1=(ss1+s1[i])%NN,ss2=(ss2+s2[i])%NN,
mxx=max(mxx,mx[i]),mnn=min(mnn,mn[i]);
// cout<<mnn<<" "<<mxx<<"!!!!\n";
if(ss2*mi(bs,mxx+mnn)%NN==ss1)cout<<"Yes\n";
else cout<<"No\n";
}
}
}