QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884056#9774. Same SumqwertimRE 189ms29288kbC++205.7kb2025-02-05 21:07:392025-02-05 21:07:42

Judging History

This is the latest submission verdict.

  • [2025-02-05 21:07:42]
  • Judged
  • Verdict: RE
  • Time: 189ms
  • Memory: 29288kb
  • [2025-02-05 21:07:39]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define i128 __int128
#define ull unsigned long long
#define ll long long
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
#define sqrt __builtin_sqrt
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define tiii tuple<int,int,int>
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof a)
#define Gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,__SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
namespace io{const int __SIZE=(1<<21)+1;char ibuf[__SIZE],*iS,*iT,obuf[__SIZE],*oS=obuf,*oT=oS+__SIZE-1,__c,qu[55];int __f,qr,_eof;inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}inline void gc(char&x){x=Gc();}inline void pc(char x){*oS++=x;if(oS==oT)flush();}inline void pstr(const char*s){int __len=strlen(s);for(__f=0;__f<__len;++__f)pc(s[__f]);}inline void gstr(char *s){for(__c=Gc();__c<32||__c>126||__c==' ';)__c=Gc();for(;__c>31&&__c<127&&__c!=' '&&__c!='\n'&&__c!='\r';++s,__c=Gc())*s=__c;*s=0;}template<class I>inline bool gi(I&x){_eof=0;for(__f=1,__c=Gc();(__c<'0'||__c>'9')&&!_eof;__c=Gc()){if(__c=='-')__f=-1;_eof|=__c==EOF;}for(x=0;__c<='9'&&__c>='0'&&!_eof;__c=Gc())x=x*10+(__c&15),_eof|=__c==EOF;x*=__f;return!_eof;}template<class I>inline void print(I x){if(!x)pc('0');if(x<0)pc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)pc(qu[qr--]);}struct Flusher_{~Flusher_(){flush();}}io_flusher_;}using io::pc;using io::gc;using io::pstr;using io::gstr;using io::gi;using io::print;
template<typename T>void cmax(T&x,T y){x=max(x,y);}template<typename T>void cmin(T&x,T y){x=min(x,y);}
#ifdef QWERTIM
namespace __DEBUG_UTIL__{template<typename T>concept is_iterable=requires(T&&x){begin(x);}&&!is_same_v<remove_cvref_t<T>,string>;void print(const char*x){cerr<<x;}void print(char x){cerr<<"\'"<<x<<"\'";}void print(bool x){cerr<<(x?"T":"F");}void print(string x){cerr<<"\""<<x<<"\"";}void print(vector<bool>&&v){int f=0;cerr<<'{';for(auto&&i:v)cerr<<(f++?",":"")<<(i?"T":"F");cerr<<"}";}template<typename T>void print(T&&x){if constexpr(is_iterable<T>)if(size(x)&&is_iterable<decltype(*(begin(x)))>){int f=0;cerr<<"\n~~~~~\n";for(auto&&i:x)cerr<<setw(2)<<left<<f++,print(i),cerr<<"\n";cerr<<"~~~~~\n";}else{int f=0;cerr<<"{";for(auto&&i:x)cerr<<(f++?",":""),print(i);cerr<<"}";}else if constexpr(requires{x.pop();}){auto temp=x;int f=0;cerr<<"{";if constexpr(requires{x.top();})while(!temp.empty())cerr<<(f++?",":""),print(temp.top()),temp.pop();else while(!temp.empty())cerr<<(f++?",":""),print(temp.front()),temp.pop();cerr<<"}";}else if constexpr(requires{x.first;x.second;})cerr<<'(',print(x.first),cerr<<',',print(x.second),cerr<<')';else if constexpr(requires{get<0>(x);}){int f=0;cerr<<'(',apply([&f](auto...args){((cerr<<(f++?",":""),print(args)),...);},x),cerr<<')';}else cerr<<x;}template<typename T,typename...V>void printer(const char*names,T&&head,V&&...tail){int i=0;for(size_t bracket=0;names[i]!='\0'&&(names[i]!=','||bracket!=0);i++)if(names[i]=='('||names[i]=='<'||names[i]=='{')bracket++;else if(names[i]==')'||names[i]=='>'||names[i]=='}')bracket--;cerr.write(names,i)<<" = ",print(head);if constexpr(sizeof...(tail))cerr<<" ||",printer(names+i+1,tail...);else cerr<<"]\n";}template<typename T,typename...V>void printerArr(const char*names,T arr[],size_t N,V...tail){size_t i=0;for(;names[i]&&names[i]!=',';i++)cerr<<names[i];for(i++;names[i]&&names[i]!=',';i++);cerr<<" = {";for(size_t ind=0;ind<N;ind++)cerr<<(ind?",":""),print(arr[ind]);cerr<<"}";if constexpr(sizeof...(tail))cerr<<" ||",printerArr(names+i+1,tail...);else cerr<<"]\n";}}
#define debug(...) cerr<<'\n'<<__LINE__<<": [",__DEBUG_UTIL__::printer(#__VA_ARGS__,__VA_ARGS__)
#define debugArr(...) cerr<<'\n'<<__LINE__<<": [",__DEBUG_UTIL__::printerArr(#__VA_ARGS__,__VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif
#define mod 998244853
int n,q,a,opt,l,r,x;
inline int qp(int x,int y=mod-2){
	int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		x=1ll*x*x%mod,y>>=1;
	}
	return ans;
}
mt19937 rnd(time(0));
int k,pw[200005],inv[200005];
void init(){
	k=rnd()%mod,pw[0]=inv[0]=1;
	fo(i,1,200000)pw[i]=1ll*pw[i-1]*k%mod;
	inv[200000]=qp(pw[200000]);
	fd(i,199999,1)inv[i]=1ll*inv[i+1]*k%mod;
}
struct segtree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	#define mid (l+r>>1)
	ll tr[1000005],lazy[1000005];
	int tr2[2][1000005];
	inline void pushup(int x){
		tr[x]=tr[ls]+tr[rs];
		fo(i,0,1)tr2[i][x]=(tr2[i][ls]+tr2[i][rs])%mod;
	}
	inline void hard(int x,int l,int r,int k){
		tr[x]+=k*(r-l+1);
		tr2[0][x]=1ll*tr2[0][x]*pw[k]%mod;
		tr2[1][x]=1ll*tr2[1][x]*inv[k]%mod;
		lazy[x]+=k;
	}
	inline void pushdown(int x,int l,int r){
		if(lazy[x])
			hard(ls,l,mid,lazy[x]),hard(rs,mid+1,r,lazy[x]),lazy[x]=0;
	}
	void build(int x,int l,int r){
		if(l==r)return gi(a),tr[x]=a,tr2[0][x]=pw[a],tr2[1][x]=inv[a],void();
		build(ls,l,mid),build(rs,mid+1,r),pushup(x);
	}
	void update(int x,int l,int r,int ql,int qr,int k){
		if(ql<=l&&r<=qr)return hard(x,l,r,k);
		pushdown(x,l,r);
		if(ql<=mid)update(ls,l,mid,ql,qr,k);
		if(mid<qr)update(rs,mid+1,r,ql,qr,k);
		pushup(x);
	}
	int query(int x,int l,int r,int ql,int qr,int ty){
		if(ql<=l&&r<=qr)return !ty?tr[x]:tr2[ty-1][x];
		pushdown(x,l,r);
		int ret=0;
		if(ql<=mid)ret+=query(ls,l,mid,ql,qr,ty);
		if(mid<qr)ret+=query(rs,mid+1,r,ql,qr,ty);
		return ret%mod;
	}
}seg;
int main(){
	init(),gi(n),gi(q),seg.build(1,1,n);
	while(q--){
		gi(opt),gi(l),gi(r);
		if(opt==1)gi(x),seg.update(1,1,n,l,r,x);
		else{
			ll avg=seg.query(1,1,n,l,r,0);
			int lhs=seg.query(1,1,n,l,r,1),rhs=seg.query(1,1,n,l,r,2);
			bool ok;
			if(avg%((r-l+1)>>1))ok=0;
			else avg/=(r-l+1)>>1,ok=(lhs==1ll*qp(k,avg)*rhs%mod);
			pstr(ok?"YES\n":"NO\n");
		}
	}
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 189ms
memory: 29288kb

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:

ok 100047 token(s): yes count is 22, no count is 100025

Test #3:

score: 0
Accepted
time: 189ms
memory: 27600kb

input:

200000 200000
5 5 2 0 1 1 4 1 1 0 4 2 2 5 5 4 1 2 2 0 3 3 3 2 5 4 1 5 1 0 0 4 3 4 2 2 3 1 4 2 0 5 4 0 2 5 5 5 2 2 3 4 0 2 2 5 0 2 3 5 4 0 0 2 1 0 5 3 1 4 5 2 2 3 4 5 0 5 5 5 3 3 0 1 4 3 0 0 3 2 2 0 4 5 5 5 2 4 5 2 5 3 1 1 5 2 1 0 1 0 5 0 0 1 5 1 5 3 1 5 3 5 4 0 2 2 4 2 5 2 3 4 5 4 3 5 2 5 2 4 5 3 4 ...

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:

ok 99734 token(s): yes count is 10, no count is 99724

Test #4:

score: -100
Runtime Error

input:

200000 200000
185447 70128 80288 38126 188018 126450 46081 189881 15377 21028 12588 100061 7218 74518 162803 34448 90998 44793 167718 16370 136024 153269 186316 137564 3082 169700 175712 19214 82647 72919 170919 142138 57755 168197 81575 126456 183138 106882 167154 184388 198667 190302 188371 183732...

output:


result: