QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#859740#9774. Same SumZZ_zuozheWA 1533ms23844kbC++172.2kb2025-01-17 22:32:042025-01-17 22:32:13

Judging History

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

  • [2025-01-17 22:32:13]
  • 评测
  • 测评结果:WA
  • 用时:1533ms
  • 内存:23844kb
  • [2025-01-17 22:32:04]
  • 提交

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]