QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1301 | #824482 | #9774. Same Sum | ship2077 | ucup-team3161 | Success! | 2024-12-23 09:43:25 | 2024-12-23 09:47:02 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 32456kb
input:
520 1 0 25844 41452 100000 0 19877 6623 100000 0 27919 26550 100000 0 30876 10014 100000 0 47835 29485 100000 0 28336 14183 100000 0 3974 27287 100000 0 25618 37957 100000 0 7307 24195 100000 0 33264 11277 100000 0 28894 40741 100000 0 33536 35437 100000 0 33466 36307 100000 0 208 33816 100000 0 164...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#824482 | #9774. Same Sum | ucup-team3161# | WA | 549ms | 92884kb | C++17 | 3.5kb | 2024-12-21 14:22:44 | 2024-12-23 09:49:08 |
answer
#include<bits/stdc++.h>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (int i=(x);i<(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PA;
inline ll read(){
ll x;
scanf("%lld",&x);
return x;
}
#define int ll
const int N = 2e5+10;
int n,q,a[N];
const int base = 2333;
inline int Mod(int x,int mod){
return x>=mod?x-mod:x;
}
inline int power(int a,ll b,int mod){
b%=mod-1;
int ret=1;
for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
return ret;
}
struct SGT{
int mod,invb;
ll mx[N<<2],mn[N<<2],tag[N<<2],tag1[N<<2],tag2[N<<2],s1[N<<2],s2[N<<2];
inline void init(int _mod){
mod=_mod;
invb=power(base,mod-2,mod);
}
inline void push_up(int u){
mx[u]=max(mx[u<<1],mx[u<<1^1]);
mn[u]=min(mn[u<<1],mn[u<<1^1]);
s1[u]=Mod(s1[u<<1]+s1[u<<1^1],mod);
s2[u]=Mod(s2[u<<1]+s2[u<<1^1],mod);
}
inline void Build(int u,int l,int r){
tag1[u]=1;
tag2[u]=1;
tag[u]=0;
if (l==r){
mx[u]=mn[u]=a[l];
s1[u]=power(base,a[l],mod);
s2[u]=power(invb,a[l],mod);
return;
}
int mid=l+r>>1;
Build(u<<1,l,mid);
Build(u<<1^1,mid+1,r);
push_up(u);
}
inline void upd(int u,ll x,ll y,ll z){
tag[u]+=x;
tag1[u]=1ll*tag1[u]*y%mod;
tag2[u]=1ll*tag2[u]*z%mod;
mn[u]+=x;
mx[u]+=x;
s1[u]=1ll*s1[u]*y%mod;
s2[u]=1ll*s2[u]*z%mod;
}
inline void push_down(int u){
if (!tag[u]) return;
upd(u<<1,tag[u],tag1[u],tag2[u]);
upd(u<<1^1,tag[u],tag1[u],tag2[u]);
tag[u]=0;
tag1[u]=1;
tag2[u]=1;
}
inline void update(int u,int l,int r,int ql,int qr,int x,int pw1,int pw2){
if (l>=ql&&r<=qr){
upd(u,x,pw1,pw2);
return;
}
int mid=l+r>>1;
push_down(u);
if (ql<=mid) update(u<<1,l,mid,ql,qr,x,pw1,pw2);
if (qr>mid) update(u<<1^1,mid+1,r,ql,qr,x,pw1,pw2);
push_up(u);
}
inline void update(int l,int r,int x){
update(1,1,n,l,r,x,power(base,x,mod),power(invb,x,mod));
}
inline PA Query1(int u,int l,int r,int ql,int qr){
if (l>=ql&&r<=qr) return mp(mn[u],mx[u]);
int mid=l+r>>1;
push_down(u);
if (qr<=mid) return Query1(u<<1,l,mid,ql,qr);
if (ql>mid) return Query1(u<<1^1,mid+1,r,ql,qr);
auto L=Query1(u<<1,l,mid,ql,qr),R=Query1(u<<1^1,mid+1,r,ql,qr);
return mp(min(L.fi,R.fi),max(L.se,R.se));
}
inline PA Query2(int u,int l,int r,int ql,int qr){
if (l>=ql&&r<=qr) return mp(s1[u],s2[u]);
int mid=l+r>>1;
push_down(u);
if (qr<=mid) return Query2(u<<1,l,mid,ql,qr);
if (ql>mid) return Query2(u<<1^1,mid+1,r,ql,qr);
auto L=Query2(u<<1,l,mid,ql,qr),R=Query2(u<<1^1,mid+1,r,ql,qr);
return mp(Mod(L.fi+R.fi,mod),Mod(L.se+R.se,mod));
}
inline bool check(int s1,int s2,ll mn,ll mx){
s1=1ll*s1*power(invb,mn,mod)%mod;
s2=1ll*s2*power(base,mx,mod)%mod;
return s1==s2;
}
}T1,T2;
signed main(){
//freopen("data.in","r",stdin);
//freopen("g.out","w",stdout);
n=read(),q=read();
For(i,1,n) a[i]=read();
T1.init(1e9+7);
T2.init(1e9+9);
T1.Build(1,1,n);
T2.Build(1,1,n);
while (q--){
int op=read(),l=read(),r=read();
if (op==1){
int x=read();
T1.update(l,r,x);
T2.update(l,r,x);
} else {
auto [mn,mx]=T1.Query1(1,1,n,l,r);
PA t=T1.Query2(1,1,n,l,r);
if (!T1.check(t.fi,t.se,mn,mx)){
puts("NO");
continue;
}
t=T2.Query2(1,1,n,l,r);
if (!T2.check(t.fi,t.se,mn,mx)){
puts("NO");
continue;
}
puts("YES");
}
}
}