QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#835853 | #9774. Same Sum | nb_jzy | WA | 950ms | 27532kb | C++14 | 2.5kb | 2024-12-28 15:04:27 | 2024-12-28 15:04:27 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
const int mod=1e9+7,P=19260817,maxn=5e5+5,inf=1e12;
int n,q,a[maxn],t[maxn<<2][2],la[maxn<<2],sum[maxn<<2];
struct node{
int sum,p1,p2;
};
int poww(int x,int y){
int res=1;
while(y>0){
if(y&1){
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
void shutdown(int p,int l,int r){
if(la[p]>0){
la[ls(p)]+=la[p],la[rs(p)]+=la[p];
int mid=(l+r)>>1;
sum[ls(p)]+=la[p]*(mid-l+1),sum[rs(p)]+=la[p]*(r-mid);
int mi=poww(P,la[p]);
t[ls(p)][0]=t[ls(p)][0]*mi%mod;t[rs(p)][0]=t[rs(p)][0]*mi%mod;
mi=poww(mi,mod-2);
t[ls(p)][1]=t[ls(p)][1]*mi%mod,t[rs(p)][1]==t[rs(p)][1]*mi%mod;
la[p]=0;
}
}
void build(int p,int l,int r){
if(l==r){
t[p][0]=poww(P,a[l]);t[p][1]=poww(P,inf-a[l]);sum[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%mod;
t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%mod;
sum[p]=sum[ls(p)]+sum[rs(p)];
}
void add(int p,int l,int r,int x,int y,int z){
if(l>=x&&r<=y){
la[p]+=z;
int mi=poww(P,z);
t[p][0]=t[p][0]*mi%mod;t[p][1]=t[p][1]*poww(mi,mod-2)%mod;
sum[p]+=(r-l+1)*z;
return;
}
shutdown(p,l,r);
int mid=(l+r)>>1;
if(x<=mid&&y>=l){
add(ls(p),l,mid,x,y,z);
}
if(y>mid&&x<=r){
add(rs(p),mid+1,r,x,y,z);
}
t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%mod;
t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%mod;
sum[p]=sum[ls(p)]+sum[rs(p)];
}
node query(int p,int l,int r,int x,int y){
if(l>=x&&r<=y){
return {sum[p],t[p][0],t[p][1]};
}
shutdown(p,l,r);
int mid=(l+r)>>1;
node res={0,0,0},ll;
if(x<=mid&&y>=l){
ll=query(ls(p),l,mid,x,y);
res.sum+=ll.sum,res.p1+=ll.p1,res.p2+=ll.p2;
}
if(y>mid&&x<=r){
ll=query(rs(p),mid+1,r,x,y);
res.sum+=ll.sum,res.p1+=ll.p1,res.p2+=ll.p2;
}
res.p1%=mod,res.p2%=mod;
return res;
}
signed main(){
// freopen("1.in","r",stdin);
int cnt=0;
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(q--){
int op,l,r,v;
cin>>op;
if(op==1){
cin>>l>>r>>v;
add(1,1,n,l,r,v);
}
else{
cin>>l>>r;
cnt++;
node res=query(1,1,n,l,r);
if(res.sum%((r-l+1)/2)==0){
int del=res.sum/((r-l+1)/2);
del=poww(poww(P,inf-del),mod-2);
if(res.p2*del%mod==res.p1){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
else{
if(cnt==464){
return 1;
}
cout<<"NO\n";
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7656kb
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: -100
Wrong Answer
time: 950ms
memory: 27532kb
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:
wrong answer expected YES, found NO [464th token]