QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1307 | #826999 | #9774. Same Sum | ship2077 | rqoi031 | Success! | 2024-12-23 16:23:34 | 2024-12-23 16:23:36 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 3612kb
input:
268 1 241 241 296 429 440 440 466 644 691 731 801 820 918 991 1051 1161 1309 1475 1561 1599 1806 1806 1874 1899 2004 2071 2072 2745 2810 2940 2955 3115 3115 3157 3207 3401 3416 3628 3990 3992 4137 4148 4150 4150 4289 4329 4356 4494 4498 4555 4585 4851 4851 4921 4950 5041 5100 5375 5542 5827 6051 605...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#826999 | #9774. Same Sum | rqoi031 | WA | 517ms | 31160kb | C++20 | 3.4kb | 2024-12-22 18:15:52 | 2024-12-23 16:29:54 |
answer
#include<stdio.h>
#include<algorithm>
typedef unsigned long long ull;
typedef __uint128_t ulll;
constexpr ull mod{1000000000000000003};
constexpr ull plus(const ull &x,const ull &y) {
if(x+y>=mod) {
return x+y-mod;
}
return x+y;
}
constexpr ull power(ull x,ull y) {
ull s{1};
while(y>0) {
if(y&1) {
s=ulll(s)*x%mod;
}
x=ulll(x)*x%mod;
y>>=1;
}
return s;
}
constexpr ull seed{998244353},iseed{power(seed,mod-2)};
constexpr int N{200000},L{1<<std::__lg(N-1)+1};
struct result {
ull sum,hsh0,hsh1;
constexpr result operator+(const result &x) const {
return result{sum+x.sum,plus(hsh0,x.hsh0),plus(hsh1,x.hsh1)};
}
};
struct node {
int len;
ull sum,add;
ull hsh0,mul0;
ull hsh1,mul1;
constexpr operator result() const {
return result{sum,hsh0,hsh1};
}
};
node tr[L<<1|1];
int a[N+5];
inline void add_tag(const int &p,const ull &x,const ull &y0,const ull &y1) {
tr[p].sum+=x*tr[p].len,tr[p].add+=x;
tr[p].hsh0=ulll(y0)*tr[p].hsh0%mod;
tr[p].mul0=ulll(y0)*tr[p].mul0%mod;
tr[p].hsh1=ulll(y1)*tr[p].hsh1%mod;
tr[p].mul1=ulll(y1)*tr[p].mul1%mod;
}
inline void push_down(const int &p) {
if(tr[p].add!=0) {
add_tag(p<<1,tr[p].add,tr[p].mul0,tr[p].mul1);
add_tag(p<<1|1,tr[p].add,tr[p].mul0,tr[p].mul1);
tr[p].add=0,tr[p].mul0=tr[p].mul1=1;
}
}
inline void push_up(const int &p) {
tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
tr[p].hsh0=plus(tr[p<<1].hsh0,tr[p<<1|1].hsh0);
tr[p].hsh1=plus(tr[p<<1].hsh1,tr[p<<1|1].hsh1);
}
void build(const int &p,const int &L,const int &R) {
tr[p].len=R-L+1;
tr[p].add=0,tr[p].mul0=tr[p].mul1=1;
if(L==R) {
tr[p].sum=a[L];
tr[p].hsh0=power(seed,a[L]);
tr[p].hsh1=power(iseed,a[L]);
return;
}
int M{L+R>>1};
build(p<<1,L,M);
build(p<<1|1,M+1,R);
push_up(p);
}
void modify(const int &p,const int &L,const int &R,const int &l,const int &r,const ull &x,const ull &y0,const ull &y1) {
if(l<=L&&r>=R) {
return add_tag(p,x,y0,y1);
}
int M{L+R>>1};
push_down(p);
if(l<=M) {
modify(p<<1,L,M,l,r,x,y0,y1);
}
if(r>M) {
modify(p<<1|1,M+1,R,l,r,x,y0,y1);
}
push_up(p);
}
result query(const int &p,const int &L,const int &R,const int &l,const int &r) {
if(l<=L&&r>=R) {
return tr[p];
}
int M{L+R>>1};
push_down(p);
if(r<=M) {
return query(p<<1,L,M,l,r);
}
if(l>M) {
return query(p<<1|1,M+1,R,l,r);
}
return query(p<<1,L,M,l,r)+query(p<<1|1,M+1,R,l,r);
}
int main() {
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) {
scanf("%d",a+i);
}
build(1,1,n);
for(int i=1;i<=q;i++) {
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1) {
int v;
scanf("%d",&v);
modify(1,1,n,l,r,v,power(seed,v),power(iseed,v));
}
else if(op==2) {
if(r-l+1&1) {
puts("NO");
continue;
}
auto [s,x,y](query(1,1,n,l,r));
if(s%(r-l+1>>1)!=0) {
puts("NO");
continue;
}
ull t{s/(r-l+1>>1)};
puts(x==ulll(y)*power(seed,t)%mod?"YES":"NO");
}
}
return 0;
}