QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#852338#9774. Same SumWanyeWA 632ms47592kbC++144.4kb2025-01-11 11:25:552025-01-11 11:25:55

Judging History

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

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2025-01-11 11:25:55]
  • 评测
  • 测评结果:WA
  • 用时:632ms
  • 内存:47592kb
  • [2025-01-11 11:25:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
#define N 200005
using namespace std;
inline char nc(){
	static char buf[1000000],*p=buf,*q=buf;
	return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
	ll res = 0,w = 1;
	char c = nc();
	while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
	while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
	return res*w;
}
char obuf[1<<21],*p3=obuf; 
inline void pc(char c){ 
	p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); 
} 
inline void write(ll x){ 
	if(x<0) pc('-'),x=-x; 
	if(x>9) write(x/10); 
	pc(x%10+'0'); 
}
struct node{ll s1,s2,s3,s4,s5;}tr[N<<2];
bool operator==(const node&a,const node&b){return a.s1==b.s1&&a.s2==b.s2&&a.s3==b.s3&&a.s4==b.s4&&a.s5==b.s5;}
node operator+(const node&a,const node&b){return (node){(a.s1+b.s1)%mod,(a.s2+b.s2)%mod,(a.s3+b.s3)%mod,(a.s4+b.s4)%mod,(a.s5+b.s5)%mod};}
ll n,q,i,a[N],opt,l,r,c,tag1[N<<2],tag2[N<<2],sum[N<<2];
inline void pushup(ll p){
	tr[p] = tr[2*p]+tr[2*p+1];
	sum[p] = sum[2*p]+sum[2*p+1];
}
inline void pushtag(ll p,ll s,ll t,ll t1,ll t2){
	if(t1!=1) sum[p]*=-1,tag1[p]*=-1,tag2[p]*=-1;
	sum[p]+=t2*(t-s+1),tag2[p]+=t2;
	t2 = (t2%mod+mod)%mod,t1 = (t1%mod+mod)%mod;
	tr[p].s1 *= t1,tr[p].s2 *= t1*t1%mod,tr[p].s3 *= t1*t1%mod*t1%mod,tr[p].s4 *= t1*t1%mod*t1%mod*t1%mod,tr[p].s5 *= t1*t1%mod*t1%mod*t1%mod*t1%mod;
	tr[p].s1 %= mod,tr[p].s2 %= mod,tr[p].s3 %= mod,tr[p].s4 %= mod,tr[p].s5 %= mod;
	tag2[p] += t2,tag2[p] %= mod;
	ll p0 = 1,p1 = p0*t2%mod,p2 = p1*t2%mod,p3 = p2*t2%mod,p4 = p3*t2%mod,p5 = p4*t2%mod;
	tr[p].s5 = (tr[p].s5+tr[p].s4*5%mod*p1%mod+tr[p].s3*10%mod*p2%mod+tr[p].s2*10%mod*p3%mod+tr[p].s1*5%mod*p4%mod+(t-s+1)*p5%mod)%mod;
	tr[p].s4 = (tr[p].s4+tr[p].s3*4%mod*p1%mod+tr[p].s2*6%mod*p2%mod+tr[p].s1*4%mod*p3%mod+(t-s+1)*p4%mod)%mod;
	tr[p].s3 = (tr[p].s3+tr[p].s2*3%mod*p1%mod+tr[p].s1*3%mod*p2%mod+(t-s+1)*p3%mod)%mod;
	tr[p].s2 = (tr[p].s2+tr[p].s1*2%mod*p1%mod+(t-s+1)*p2%mod)%mod;
	tr[p].s1 = (tr[p].s1+(t-s+1)*p1)%mod;
	tr[p].s1 = (tr[p].s1%mod+mod)%mod;
	tr[p].s2 = (tr[p].s2%mod+mod)%mod;
	tr[p].s3 = (tr[p].s3%mod+mod)%mod;
	tr[p].s4 = (tr[p].s4%mod+mod)%mod;
	tr[p].s5 = (tr[p].s5%mod+mod)%mod;
}
inline void pushdown(ll p,ll s,ll t){
	pushtag(2*p,s,(s+t)/2,tag1[p],tag2[p]);
	pushtag(2*p+1,(s+t)/2+1,t,tag1[p],tag2[p]);
	tag1[p] = 1,tag2[p] = 0;
}
inline void build(ll s,ll t,ll p){
	tag1[p] = 1,tag2[p] = 0;
	if(s==t){
		sum[p] = a[s];
		tr[p].s1 = a[s]%mod,tr[p].s2 = a[s]*a[s]%mod,tr[p].s3 = a[s]*a[s]%mod*a[s]%mod;
		tr[p].s4 = a[s]*a[s]%mod*a[s]%mod*a[s]%mod;
		tr[p].s5 = tr[p].s4*a[s]%mod;
		return ;
	}
	build(s,(s+t)/2,2*p),build((s+t)/2+1,t,2*p+1);
	pushup(p);
}
inline void add(ll l,ll r,ll c,ll s,ll t,ll p){
	if(l<=s&&t<=r) return pushtag(p,s,t,1,c);
	if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
	if(l<=(s+t)/2) add(l,r,c,s,(s+t)/2,2*p);
	if(r>(s+t)/2) add(l,r,c,(s+t)/2+1,t,2*p+1);
	pushup(p);
}
inline ll get_sum(ll l, ll r, ll s, ll t, ll p) {
	if (l <= s && t <= r) return sum[p];
	if (tag1[p] != 1 || tag2[p]) pushdown(p, s, t);
	ll res = 0;
	if (l <= (s + t) / 2) res += get_sum(l, r, s, (s + t) / 2, 2 * p);
	if (r > (s + t) / 2) res += get_sum(l, r, (s + t) / 2 + 1, t, 2 * p + 1);
	return res;
}
inline void change(ll l,ll r,ll s,ll t,ll p){
	if(l<=s&&t<=r) return pushtag(p,s,t,-1,0);
	if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
	if(l<=(s+t)/2) change(l,r,s,(s+t)/2,2*p);
	if(r>(s+t)/2) change(l,r,(s+t)/2+1,t,2*p+1);
	pushup(p);
}
inline node query(ll l,ll r,ll s,ll t,ll p){
	if(l<=s&&t<=r) return tr[p];
	if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
	if(l<=(s+t)/2&&r>(s+t)/2) return query(l,r,s,(s+t)/2,2*p)+query(l,r,(s+t)/2+1,t,2*p+1);
	else if(l<=(s+t)/2) return query(l,r,s,(s+t)/2,2*p);
	else return query(l,r,(s+t)/2+1,t,2*p+1);
}
int main(){
	n=read(),q=read();
	for(i=1;i<=n;i++) a[i]=read();
	build(1,n,1);
	while(q--){
		opt=read();
		if(opt==1){
			l = read(),r = read(),c = read();
			add(l,r,c,1,n,1);
		}
		if(opt==2){
			l = read(),r = read();
			ll num = get_sum(l,r,1,n,1);
			if(num%((r-l+1)/2)!=0){
				pc('N'),pc('O'),pc('\n');
				continue;
			}
			ll Deltaa = num/((r-l+1)/2);
			node tmp1 = query(l,r,1,n,1);
			change(l,r,1,n,1),add(l,r,Deltaa,1,n,1);
			node tmp2 = query(l,r,1,n,1);
			add(l,r,-Deltaa,1,n,1),change(l,r,1,n,1);
			if(tmp1==tmp2) pc('Y'),pc('E'),pc('S'),pc('\n');
			else pc('N'),pc('O'),pc('\n');
		}
	}
	return fwrite(obuf,p3-obuf,1,stdout),0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 13864kb

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: 632ms
memory: 47592kb

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]