QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#856944 | #9774. Same Sum | yuanyq5523 | WA | 1031ms | 100984kb | C++14 | 3.5kb | 2025-01-14 21:09:37 | 2025-01-14 21:09:42 |
Judging History
answer
#include <bits/stdc++.h>
#define endl "\n"
#define LL long long
using namespace std;
const int N=2e5+5;
int n,q,b[N];
struct segmentTree{
int op,kd;
LL P,mod,a[N],tr[N<<2],tag[N<<2];
LL quick_pow(LL a,LL b){
LL res=1;
while (b){
if (b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void push_up(int u){
tr[u]=(tr[u<<1]+tr[u<<1|1]);
if (op==1) tr[u]%=mod;
}
void push_down(int u,int l,int r){
if (op==0){
if (tag[u]!=0){
int mid=(l+r)>>1;
tr[u<<1]+=tag[u]*(r-mid);
tr[u<<1|1]+=tag[u]*(mid-l+1);
tag[u<<1]+=tag[u]; tag[u<<1|1]+=tag[u];
tag[u]=0; return;
}
}
else{
if (tag[u]!=1){
tr[u<<1]=tr[u<<1]*tag[u]%mod;
tr[u<<1|1]=tr[u<<1|1]*tag[u]%mod;
tag[u<<1]=tag[u<<1]*tag[u]%mod;
tag[u<<1|1]=tag[u<<1|1]*tag[u]%mod;
tag[u]=1;
}
}
}
void build(int u,int l,int r){
tag[u]=op; tr[u]=0;
if (l==r){
tr[u]=a[l];
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int L,int R,LL v){
if (l>R || r<L) return;
if (L<=l && r<=R){
if (op==0){
tr[u]+=v*(r-l+1);
tag[u]+=v;
return;
}
else{
tr[u]=tr[u]*v%mod;
tag[u]=tag[u]*v%mod;
return;
}
}
push_down(u,l,r);
int mid=(l+r)>>1;
update(u<<1,l,mid,L,R,v);
update(u<<1|1,mid+1,r,L,R,v);
push_up(u);
}
LL query(int u,int l,int r,int L,int R){
if (l>R || r<L) return 0;
if (L<=l && r<=R) return tr[u];
push_down(u,l,r);
int mid=(l+r)>>1;
LL res=query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);
if (op==1) res%=mod;
return res;
}
void prework(int cop,int ckd,LL cP,LL cmod){
op=cop; kd=ckd; P=cP; mod=cmod;
for (int i=1;i<=n;i++){
a[i]=b[i];
if (ckd==1) a[i]=quick_pow(P,a[i]);
if (ckd==2) a[i]=quick_pow(quick_pow(P,a[i]),mod-2);
}
build(1,1,n);
}
void update(int l,int r,LL v){
if (kd==0) update(1,1,n,l,r,v);
else{
v=quick_pow(P,v);
if (kd==1) update(1,1,n,l,r,v);
else{
v=quick_pow(v,mod-2);
update(1,1,n,l,r,v);
}
}
}
}s,segp1,segp2,segp3,segn1,segn2,segn3;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;i++) cin>>b[i];
s.prework(0,0,0,0);
segp1.prework(1,1,100523,1e9+21);
segp2.prework(1,1,1000639,1e9+181);
segp3.prework(1,1,1e8+81,1e9+459);
segn1.prework(1,2,100523,1e9+21);
segn2.prework(1,2,1000639,1e9+181);
segn3.prework(1,2,1e8+81,1e9+459);
while (q--){
int op; cin>>op;
if (op==1){
int l,r; LL v; cin>>l>>r>>v;
s.update(l,r,v);
segp1.update(l,r,v);
segp2.update(l,r,v);
segp3.update(l,r,v);
segn1.update(l,r,v);
segn2.update(l,r,v);
segn3.update(l,r,v);
}
else{
int l,r; cin>>l>>r;
LL sum=s.query(1,1,n,l,r);
if (sum*2%(r-l+1)!=0){
cout<<"No"<<endl;
continue;
}
LL ave=sum*2/(r-l+1);
LL q1=segp1.query(1,1,n,l,r),q2=segn1.query(1,1,n,l,r);
LL q3=segp2.query(1,1,n,l,r),q4=segn2.query(1,1,n,l,r);
LL q5=segp3.query(1,1,n,l,r),q6=segn3.query(1,1,n,l,r);
bool check1=(q1==q2*segn1.quick_pow(segn1.P,ave)%segn1.mod);
bool check2=(q3==q4*segn2.quick_pow(segn2.P,ave)%segn2.mod);
bool check3=(q5==q6*segn3.quick_pow(segn3.P,ave)%segn3.mod);
// cout<<q1<<" "<<q2<<" "<<q3<<" "<<q4<<" "<<check1<<" "<<check2<<endl;
if (check1 && check2 && check3) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 42680kb
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: 1031ms
memory: 100984kb
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]