QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1305 | #827678 | #9774. Same Sum | ship2077 | dxbt | Success! | 2024-12-23 15:54:23 | 2024-12-23 15:54:25 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 56320kb
input:
524 1 73 240 281 284 317 388 430 820 826 872 876 947 950 1014 1072 1079 1106 1321 1501 1607 1678 1724 1753 1758 1860 1890 1948 1956 2004 2121 2142 2212 2215 2328 2351 2754 2763 2807 2809 2884 2906 2916 2998 3011 3022 3067 3130 3206 3382 3397 3537 3629 3650 3780 4014 4070 4182 4255 4297 4366 4382 442...
output:
Yes
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#827678 | #9774. Same Sum | dxbt | WA | 1214ms | 63400kb | C++14 | 3.1kb | 2024-12-23 08:06:46 | 2024-12-23 16:03:56 |
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=12331337;
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;
}