QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1304 | #823708 | #9774. Same Sum | ship2077 | ucup-team1004 | Success! | 2024-12-23 14:58:21 | 2024-12-23 14:58:21 |
Details
Extra Test:
Wrong Answer
time: 15ms
memory: 21248kb
input:
1972 1 11 14 18 29 34 49 85 105 153 167 203 205 213 216 221 223 232 239 239 268 275 282 322 328 330 353 353 369 397 462 475 475 478 489 520 535 551 588 590 595 600 615 627 634 634 647 648 659 689 692 739 746 771 776 805 814 814 822 831 835 841 851 851 854 882 895 895 903 912 993 1001 1008 1033 1048 ...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#823708 | #9774. Same Sum | ucup-team1004# | WA | 822ms | 46304kb | C++17 | 3.5kb | 2024-12-21 09:15:29 | 2024-12-23 14:59:06 |
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=2e5+10;
const int M=3;
using node=array<int,M>;
const node base={19260817,2333,181766};
const node mod={(int)1e9+7,(int)1e9+9,998244353};
ll getinv(ll x,int mod,ll ans=1){
for(int y=mod-2;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
return ans;
}
node operator * (const node &a,const node &b){
static node c;
for(int i=0;i<M;i++)c[i]=1ll*a[i]*b[i]%mod[i];
return c;
}
node operator * (const node &a,const int &k){
static node b;
for(int i=0;i<M;i++)b[i]=1ll*a[i]*k%mod[i];
return b;
}
node operator + (const node &a,const int &b){
static node c;
for(int i=0;i<M;i++)c[i]=(a[i]+b)%mod[i];
return c;
}
node operator + (const node &a,const node &b){
static node c;
for(int i=0;i<M;i++)c[i]=(a[i]+b[i])%mod[i];
return c;
}
node operator - (const node &a,const node &b){
static node c;
for(int i=0;i<M;i++)c[i]=(a[i]+mod[i]-b[i])%mod[i];
return c;
}
#ifdef DEBUG
ostream& operator << (ostream &out,node a){
out<<'(';
for(auto x:a)out<<x<<',';
return out<<')';
}
#endif
int n,m,a[N];
node ibase,pw[N],Pw[N],ipw[N],iPw[N];
void init(){
pw[0].fill(1);
for(int i=1;i<N;i++)pw[i]=pw[i-1]*base;
node b=pw[N-1]*base;
Pw[0].fill(1);
for(int i=1;i<N;i++)Pw[i]=Pw[i-1]*b;
for(int i=0;i<M;i++)ibase[i]=getinv(base[i],mod[i]);
ipw[0].fill(1);
for(int i=1;i<N;i++)ipw[i]=ipw[i-1]*ibase;
b=ipw[N-1]*ibase;
iPw[0].fill(1);
for(int i=1;i<N;i++)iPw[i]=iPw[i-1]*b;
}
node qpow(ll x){
return Pw[x/N]*pw[x%N];
}
node iqpow(ll x){
return iPw[x/N]*ipw[x%N];
}
int siz[N<<2];
ll sum[N<<2],laz[N<<2];
node s[N<<2],t[N<<2];
void pushup(int rt){
s[rt]=s[rt<<1]+s[rt<<1|1];
t[rt]=t[rt<<1]+t[rt<<1|1];
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushlaz(int rt,ll x){
sum[rt]+=x*siz[rt];
laz[rt]+=x;
s[rt]=s[rt]*qpow(x);
t[rt]=t[rt]*iqpow(x);
}
void pushdown(int rt){
if(laz[rt]){
pushlaz(rt<<1,laz[rt]);
pushlaz(rt<<1|1,laz[rt]);
laz[rt]=0;
}
}
void build(int l=1,int r=n,int rt=1){
siz[rt]=r-l+1;
laz[rt]=0;
if(l==r){
sum[rt]=a[l];
s[rt]=qpow(a[l]);
t[rt]=iqpow(a[l]);
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(int L,int R,int x,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return pushlaz(rt,x);
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)update(L,R,x,l,mid,rt<<1);
if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
void query(int L,int R,ll &res,node &f,node &g,int l=1,int r=n,int rt=1){
if(L<=l&&r<=R)return res+=sum[rt],f=f+s[rt],g=g+t[rt],void();
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid)query(L,R,res,f,g,l,mid,rt<<1);
if(mid<R)query(L,R,res,f,g,mid+1,r,rt<<1|1);
}
int main(){
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
build();
// debug(s[1]);
for(int op,l,r,x;m--;){
scanf("%d%d%d",&op,&l,&r);
if(op==1){
scanf("%d",&x);
update(l,r,x);
}else{
ll res=0;
node f,g;
f.fill(0),g.fill(0);
query(l,r,res,f,g);
// debug(l,r,f,g);
puts([&](){
if(res%((r-l+1)/2))return 0;
res/=(r-l+1)/2;
// debug(res,f,g,g*qpow(res));
if(f!=g*qpow(res))return 0;
return 1;
}()?"YES":"NO");
}
}
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif