QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1308#828389#9774. Same SumzhenghanyundxbtSuccess!2024-12-23 16:33:252024-12-23 16:33:27

Details

Extra Test:

Wrong Answer
time: 7ms
memory: 56900kb

input:

103744 1
11078 98237 74492 16193 69643 44785 82715 2857 32202 57161 78418 32219 69572 41462 46834 42132 36974 56197 26540 80289 25180 69381 95212 10227 45008 99405 23180 32407 25520 74527 75040 24913 67546 5979 34140 92335 44888 81897 36692 36523 77482 28692 17230 76596 69134 31152 32510 67204 55365...

output:

Yes

result:

wrong answer expected NO, found YES [1st token]

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#828389#9774. Same SumdxbtWA 1173ms63356kbC++143.1kb2024-12-23 16:25:512024-12-23 16:47:50

answer

#include<bits/stdc++.h>
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define pii pair<int,int>
#define x first
#define y second
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
typedef long long ll;
constexpr int mod=998244353;
struct node
{
	ll a,b,c,d,e,f,s,t;
	node(){a=b=c=d=e=0,f=1;}
	node(ll a1,ll b1,ll c1,ll d1,ll e1,ll f1,ll s1,ll t1)
	{
		s=s1,t=t1,a=a1,b=b1,c=c1,d=d1,e=e1,f=f1;
	}
	void add(ll x)
	{
		x%=mod;
		ll p1=x,p2=x*p1%mod,p3=p2*p1%mod,p4=p3*p1%mod,p5=p4*p1%mod,p6=p5*p1%mod,p7=p6*p1%mod;
		s=(s+7*t%mod*p1+21*a%mod*p2+35*b%mod*p3+35*c%mod*p4+21*d%mod*p5+7*e%mod*p6%mod+f*p7)%mod;
		t=(t+6*a%mod*p1+15*b%mod*p2+20*c%mod*p3+15*d%mod*p4+6*e%mod*p5+f*p6%mod)%mod;
		a=(a+5*b%mod*p1+10*c%mod*p2+10*d%mod*p3+5*e%mod*p4+f*p5)%mod;
		b=(b+4*c%mod*p1%mod+6*d%mod*p2+4*e%mod*p3+f*p4)%mod;
		c=(c+3*d%mod*p1%mod+3*e%mod*p2+f*p3)%mod;
		d=(d+2*e%mod*p1+f*p2)%mod;
		e=(e+f*p1)%mod;
	}
	node operator+(const node &A)const
	{
		return node{a+A.a,b+A.b,c+A.c,d+A.d,e+A.e,f+A.f,s+A.s,t+A.t};
	}
	void print()
	{
		cerr<<s<<' '<<t<<' '<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<'\n';
	}
}tr[200009<<2];
ll tag[200009<<2];
ll a[200009<<2];
ll qpow(ll x,ll y)
{
	ll res=1;
	for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;
	return res;
}
void pushdown(int o)
{
	if(tag[o])
	{
		tag[o<<1]+=tag[o];
		tag[o<<1|1]+=tag[o];
		tr[o<<1].add(tag[o]);
		tr[o<<1|1].add(tag[o]);
		tag[o]=0;
		return ;
	}
}
void add(int l,int r,int o,int a,int b,int c)
{
	if(a<=l && r<=b)return tr[o].add(c),tag[o]+=c,void();
	int mid=l+r>>1;
	pushdown(o);
	if(a<=mid)add(l,mid,o<<1,a,b,c);
	if(b>mid) add(mid+1,r,o<<1|1,a,b,c);
	tr[o]=tr[o<<1]+tr[o<<1|1];
}
ll ask(int l,int r,int o,int a,int b)
{
	if(a<=l && r<=b)return tr[o].e;
	int mid=l+r>>1;
	pushdown(o);
	if(b<=mid)return ask(l,mid,o<<1,a,b);
	if(a>mid) return ask(mid+1,r,o<<1|1,a,b);
	return (ask(l,mid,o<<1,a,b)+ask(mid+1,r,o<<1|1,a,b))%mod;
}
node ask1(int l,int r,int o,int a,int b)
{
	if(a<=l && r<=b)return tr[o];
	int mid=l+r>>1;
	pushdown(o);
	if(b<=mid)return ask1(l,mid,o<<1,a,b);
	if(a>mid) return ask1(mid+1,r,o<<1|1,a,b);
	return (ask1(l,mid,o<<1,a,b)+ask1(mid+1,r,o<<1|1,a,b));
}
void build(int l,int r,int o)
{
	if(l==r)return tr[o].add(a[l]),void();
	int mid=l+r>>1;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	tr[o]=tr[o<<1]+tr[o<<1|1];
}
int main()
{
	cin.tie(0)->sync_with_stdio(false);
	int n,q;
	cin>>n>>q;
	F(i,1,n)cin>>a[i];
	build(1,n,1);
	/*node s;
	s.print();
	s.add(1);
	s.print();
	s.add(1);
	s.print();*/
	int test=0;
	F(cc,1,q)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r,c;
			cin>>l>>r>>c;
			add(1,n,1,l,r,c);
		}
		else
		{
			test++;
			int l,r;
			cin>>l>>r;
			ll sum=ask(1,n,1,l,r)*qpow(r-l+1,mod-2)%mod;
		//	cerr<<"sum"<<sum<<'\n';
			add(1,n,1,l,r,mod-sum);
			node p=ask1(1,n,1,l,r);
		//	if(test==953)
		//	p.print();
			if(p.s%mod==0&&p.c%mod==0&&p.a%mod==0)puts("Yes");
			else puts("No");
			add(1,n,1,l,r,sum);
		}
	}
	return 0;
}