QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1293#826983#9774. Same Sumship2077huaxiamengjinFailed.2024-12-22 18:12:062024-12-22 18:12:08

Details

Extra Test:

Invalid Input

input:

200000 200000
29003 167294 24625 7788 85721 59326 33809 160366 167416 197053 140922 140603 57679 175716 80215 168687 77863 119497 104189 130968 91257 129608 3365 63935 119662 47921 177230 3318 81973 166393 150791 161770 13993 76129 121261 99733 75491 183913 104638 35403 48893 129737 66572 194370 829...

output:


result:

FAIL Integer parameter [name=v] equals to 840091, violates the range [0, 200000] (stdin, line 3)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#826983#9774. Same SumhuaxiamengjinTL 1760ms16412kbC++143.2kb2024-12-22 17:54:382024-12-22 18:26:06

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=350;
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";
        }
    }
}