QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133651 | #4940. Token Distance | S_Explosion# | WA | 3ms | 16460kb | C++20 | 3.0kb | 2023-08-02 12:24:52 | 2023-08-02 12:27:19 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define P 998244353
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
using namespace std;
const int N=100005;
int n,q,m,a[N],mx[N<<2],mn[N<<2],sum1[N<<2],sum2[N<<2];
inline int read() {
int x = 0;
bool f = true; char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
x = f ? x : -x;
return x;
}
void push_up(int k){
sum1[k]=sum1[ls(k)]+sum1[rs(k)];
sum2[k]=(sum2[ls(k)]+sum2[rs(k)]);
mx[k]=max(mx[ls(k)],mx[rs(k)]);
mn[k]=min(mn[ls(k)],mn[rs(k)]);
}
void build(int l,int r,int k){
if(l==r){
sum1[k]=mx[k]=mn[k]=a[l];
sum2[k]=a[l]*a[l]%P;
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(k));
build(mid+1,r,rs(k));
push_up(k);
}
void update(int l,int r,int x,int y,int k){
if(l==r){
sum1[k]=mx[k]=mn[k]=y;
sum2[k]=y*y%P;
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,x,y,ls(k));
else update(mid+1,r,x,y,rs(k));
push_up(k);
}
int qma(int l,int r,int x,int y,int k){
if(x<=l&&r<=y) return mx[k];
int mid=(l+r)>>1,res=-1e15;
if(x<=mid) res=max(res,qma(l,mid,x,y,ls(k)));
if(mid+1<=y) res=max(res,qma(mid+1,r,x,y,rs(k)));
return res;
}
int qmn(int l,int r,int x,int y,int k){
if(x<=l&&r<=y) return mn[k];
int mid=(l+r)>>1,res=1e15;
if(x<=mid) res=min(res,qmn(l,mid,x,y,ls(k)));
if(mid+1<=y) res=min(res,qmn(mid+1,r,x,y,rs(k)));
return res;
}
int qs1(int l,int r,int x,int y,int k){
if(x<=l&&r<=y) return sum1[k];
int mid=(l+r)>>1,res=0;
if(x<=mid) res=res+qs1(l,mid,x,y,ls(k));
if(mid+1<=y) res=res+qs1(mid+1,r,x,y,rs(k));
return res;
}
int qs2(int l,int r,int x,int y,int k){
if(x<=l&&r<=y) return sum2[k];
int mid=(l+r)>>1,res=0;
if(x<=mid) res=(res+qs2(l,mid,x,y,ls(k)))%P;
if(mid+1<=y) res=(res+qs2(mid+1,r,x,y,rs(k)))%P;
return res;
}
signed main() {
n=read(),q=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,n,1);
while(q--){
int op=read(),x=read(),y=read();
if(op==1){
update(1,n,x,y,1);
}
else{
int MA=qma(1,n,x,y,1),MN=qmn(1,n,x,y,1);
int len=y-x+1;
if(len<=2){
puts("YES");
}
else{
if((MA-MN)%(len-1)){
puts("NO");
}
else{
int k=(MA-MN)/(len-1);
int s1=qs1(1,n,x,y,1),s2=qs2(1,n,x,y,1);
int S1=len*MN+len*(len-1)/2*k;
int S2=(len*MN%P*MN%P+len*(len-1)%P*MN%P*k%P+len*(len-1)/2*(2*len-1)/3%P*k%P*k%P)%P;
// printf("%d %d %d %d\n",s1,s2,S1,S2);
if(s1==S1&&s2==S2) puts("YES");
else puts("NO");
}
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9724kb
input:
5 7 1 1 1 10 1 2 1 3 2 1 5 1 5 4 1 3 7 2 2 4 2 2 5 2 4 5
output:
YES NO NO YES YES
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 9600kb
input:
2 1 0 1000000000 2 1 2
output:
YES
result:
ok single line: 'YES'
Test #3:
score: 0
Accepted
time: 3ms
memory: 16280kb
input:
81473 13549 972586683 972586964 972587245 972587526 972587807 972588088 972588369 972588650 972588931 972589212 972589493 972589774 972590055 972590336 972590617 972590898 972591179 972591460 972591741 972592022 972592303 972592584 972592865 972593146 972593427 972593708 972593989 972594270 97259455...
output:
YES YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES NO YES NO YES NO YES YES YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES YES Y...
result:
ok 4517 lines
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 16460kb
input:
81473 13549 994993061 993089286 973546017 983608065 980300695 994305454 992559601 974765838 987574661 988923180 987601637 991357764 981678157 994388630 987066613 976087381 985770922 989296067 975698758 977548300 992236732 978102432 983875296 979745439 977111907 992622264 988921213 987697458 99145442...
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 2nd lines differ - expected: 'YES', found: 'NO'