QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#825261#9774. Same Sumucup-team073#TL 207ms117728kbC++235.2kb2024-12-21 17:54:482024-12-23 17:07:38

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2024-12-23 17:07:38]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:TL
  • 用时:207ms
  • 内存:117728kb
  • [2024-12-23 17:02:06]
  • hack成功,自动添加数据
  • (/hack/1310)
  • [2024-12-23 16:55:25]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1984ms
  • 内存:135776kb
  • [2024-12-23 16:48:26]
  • hack成功,自动添加数据
  • (/hack/1309)
  • [2024-12-23 16:40:23]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1791ms
  • 内存:135832kb
  • [2024-12-23 16:33:45]
  • hack成功,自动添加数据
  • (/hack/1308)
  • [2024-12-23 16:27:39]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1688ms
  • 内存:135940kb
  • [2024-12-23 16:23:53]
  • hack成功,自动添加数据
  • (/hack/1307)
  • [2024-12-23 16:17:04]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1911ms
  • 内存:135984kb
  • [2024-12-23 16:13:08]
  • hack成功,自动添加数据
  • (/hack/1306)
  • [2024-12-23 15:59:48]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1592ms
  • 内存:136016kb
  • [2024-12-23 15:54:42]
  • hack成功,自动添加数据
  • (/hack/1305)
  • [2024-12-23 15:03:58]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1616ms
  • 内存:132016kb
  • [2024-12-23 14:58:39]
  • hack成功,自动添加数据
  • (/hack/1304)
  • [2024-12-23 10:02:48]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1729ms
  • 内存:136064kb
  • [2024-12-23 09:58:11]
  • hack成功,自动添加数据
  • (/hack/1302)
  • [2024-12-23 09:50:42]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1738ms
  • 内存:135844kb
  • [2024-12-23 09:47:22]
  • hack成功,自动添加数据
  • (/hack/1301)
  • [2024-12-23 09:44:32]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1595ms
  • 内存:135812kb
  • [2024-12-23 09:41:23]
  • hack成功,自动添加数据
  • (/hack/1300)
  • [2024-12-23 09:29:55]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1750ms
  • 内存:135836kb
  • [2024-12-23 09:26:32]
  • hack成功,自动添加数据
  • (/hack/1299)
  • [2024-12-23 09:23:16]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1707ms
  • 内存:135804kb
  • [2024-12-23 09:19:58]
  • hack成功,自动添加数据
  • (/hack/1298)
  • [2024-12-23 09:16:46]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1683ms
  • 内存:135552kb
  • [2024-12-23 09:13:29]
  • hack成功,自动添加数据
  • (/hack/1297)
  • [2024-12-22 19:02:03]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1730ms
  • 内存:134952kb
  • [2024-12-22 18:52:18]
  • hack成功,自动添加数据
  • (/hack/1296)
  • [2024-12-22 18:21:11]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1642ms
  • 内存:135648kb
  • [2024-12-22 18:13:14]
  • hack成功,自动添加数据
  • (/hack/1294)
  • [2024-12-21 17:54:55]
  • 评测
  • 测评结果:100
  • 用时:1807ms
  • 内存:132216kb
  • [2024-12-21 17:54:48]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f^=ch=='-';
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return f?x:-x;
}
inline int qpow(int x,int t,int mo){
    int ret=1;
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
struct Hash{
    int a[4];
    Hash(int x,int y,int z,int w){
        a[0]=x,a[1]=y,a[2]=z,a[3]=w;
    }
    Hash(){a[0]=a[1]=a[2]=a[3]=0;}
    Hash operator + (Hash x){
        Hash ret;
        for(int i=0;i<4;++i)ret.a[i]=a[i]+x.a[i];
        return ret;
    }
    Hash operator - (Hash x){
        Hash ret;
        for(int i=0;i<4;++i)ret.a[i]=a[i]-x.a[i];
        return ret;
    }
    Hash operator * (Hash x){
        Hash ret;
        for(int i=0;i<4;++i)ret.a[i]=a[i]*x.a[i];
        return ret;
    }
    Hash operator % (Hash x){
        Hash ret;
        for(int i=0;i<4;++i)ret.a[i]=a[i]%x.a[i];
        return ret;
    }
    bool operator == (Hash x){
        for(int i=0;i<4;++i)if(x.a[i]!=a[i])return 0;
        return 1;
    }
    bool operator != (Hash x){
        for(int i=0;i<4;++i)if(x.a[i]!=a[i])return 1;
        return 0;
    }
};
const Hash mo(998244353,993244853,1e9+7,1e9+9);
const Hash bas(1009,997,2909,3881);
const int N=2e5+5,inf=1e12;
Hash pw[N],ipw[N];
void red(Hash &x){
    for(int i=0;i<4;++i)if(x.a[i]>=mo.a[i])
        x.a[i]-=mo.a[i];
}
int n,a[N],q;
struct SegmentTree{
    Hash val[N<<2],mdf[N<<2];
    void pushdown(int p){
        val[lc]=val[lc]*mdf[p]%mo;
        val[rc]=val[rc]*mdf[p]%mo;
        mdf[lc]=mdf[lc]*mdf[p]%mo;
        mdf[rc]=mdf[rc]*mdf[p]%mo;
        mdf[p]=Hash(1,1,1,1);
    }
    void pushup(int p){
        red(val[p]=val[lc]+val[rc]);
    }
    void modify(int p,int l,int r,int L,int R,Hash d){
        if(L<=l&&r<=R){
            val[p]=val[p]*d%mo;
            mdf[p]=mdf[p]*d%mo;
        }else{
            pushdown(p);
            int mid=(l+r)>>1;
            if(L<=mid)modify(lc,l,mid,L,R,d);
            if(mid<R)modify(rc,mid+1,r,L,R,d);
            pushup(p);
        }
    }
    Hash query(int p,int l,int r,int L,int R){
        if(L<=l&&r<=R)return val[p];
        else{
            pushdown(p);
            int mid=(l+r)>>1;
            Hash ret=Hash(0,0,0,0);
            if(L<=mid)red(ret=ret+query(lc,l,mid,L,R));
            if(mid<R)red(ret=ret+query(rc,mid+1,r,L,R));
            return ret;
        }
    }
    void build(int p,int l,int r,int tag){
        mdf[p]=Hash(1,1,1,1);
        if(l==r)val[p]=tag?pw[a[l]]:ipw[a[l]];
        else{
            int mid=(l+r)>>1;
            build(lc,l,mid,tag);
            build(rc,mid+1,r,tag);
            pushup(p);
        }
    }
}T1,T2;
struct sgt{
    int minf[N<<2],maxf[N<<2],add[N<<2];
    void pushdown(int p){
        minf[lc]+=add[p];
        minf[rc]+=add[p];
        maxf[lc]+=add[p];
        maxf[rc]+=add[p];
        add[lc]+=add[p];
        add[rc]+=add[p];
        add[p]=0;
    }
    void pushup(int p){
        minf[p]=min(minf[lc],minf[rc]);
        maxf[p]=max(maxf[lc],maxf[rc]);
    }
    void modify(int p,int l,int r,int L,int R,int d){
        if(L<=l&&r<=R){
            add[p]+=d;
            minf[p]+=d;
            maxf[p]+=d;
        }else{
            pushdown(p);
            int mid=(l+r)>>1;
            if(L<=mid)modify(lc,l,mid,L,R,d);
            if(mid<R)modify(rc,mid+1,r,L,R,d);
            pushup(p);
        }
    }
    int query1(int p,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            return minf[p];
        }else{
            pushdown(p);
            int mid=(l+r)>>1,ret=inf;
            if(L<=mid)ret=min(ret,query1(lc,l,mid,L,R));
            if(mid<R)ret=min(ret,query1(rc,mid+1,r,L,R));
            return ret;
        }
    }
    int query2(int p,int l,int r,int L,int R){
        if(L<=l&&r<=R)return maxf[p];
        else{
            pushdown(p);
            int mid=(l+r)>>1,ret=0;
            if(L<=mid)ret=max(ret,query2(lc,l,mid,L,R));
            if(mid<R)ret=max(ret,query2(rc,mid+1,r,L,R));
            return ret;
        }
    }
}arr;
Hash fpow(Hash x,int t){
    Hash ret=Hash(1,1,1,1);
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
signed main(){
    pw[0]=ipw[0]=Hash(1,1,1,1);
    for(int i=1;i<N;++i){
        pw[i]=pw[i-1]*bas%mo;
        for(int j=0;j<4;++j){
            ipw[i].a[j]=qpow(pw[i].a[j],mo.a[j]-2,mo.a[j]);
        }
    }
    n=read(),q=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        arr.modify(1,1,n,i,i,a[i]);
    }
    T1.build(1,1,n,1),T2.build(1,1,n,0);
    while(q--){
        int opt=read(),l=read(),r=read();
        if(opt==1){
            int v=read();
            arr.modify(1,1,n,l,r,v);
            T1.modify(1,1,n,l,r,pw[v]);
            T2.modify(1,1,n,l,r,ipw[v]);
        }else{
            int tmp=arr.query1(1,1,n,l,r)+arr.query2(1,1,n,l,r);
            Hash F=T1.query(1,1,n,l,r);
            Hash G=T2.query(1,1,n,l,r);
            Hash fuck=fpow(bas,tmp);
            G=G*fuck%mo;
            if(F==G)puts("YES");
            else puts("NO");
        }
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 207ms
memory: 117728kb

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
Time Limit Exceeded

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: