QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#32053 | #1465. Not Our Problem | Wu_Ren | Compile Error | / | / | Python3 | 1.6kb | 2022-05-16 20:41:31 | 2022-05-18 04:29:33 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2022-05-18 04:29:33]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2022-05-16 20:41:31]
- 提交
answer
#include <bits/stdc++.h>
const int mod=998244353;
typedef long long ll;
using namespace std;
int n,sum[2000010],K,pr[2000010];
ll m,a[500010],Lb[2000010],Rb[2000010];
ll qr(ll x){
return (m/x/x>=x)?m/x/x:min((ll)sqrtl(m/x),x-1);
}
void qmo(int &x){
x+=(x>>31)&mod;
}
int qsqrt(ll l,ll r){
int Bl=qr(l),Br=qr(r),res=pr[Br+1]-pr[Bl];qmo(res);
if(Bl==Br) return (r-l+1)%mod*(Bl+1)%mod;
return (res+(Rb[Bl]-l+1)%mod*(Bl+1)+(r-Lb[Br]+1)%mod*(Br+1))%mod;
}
inline int qry(ll l,ll r,ll x){
if(l>r) return 0;
if(l==0) return (qry(1,r,x)+x+1)%mod;
if(qr(l)>x){
ll L=l,R=r,mid,ans=l;
while(L<=R){
mid=(L+R)>>1;
if(qr(mid)>x) L=mid+1,ans=mid;
else R=mid-1;
}
return (qry(ans+1,r,x)+(x+1)%mod*((ans-l+1)%mod))%mod;
}
if(m/l/l>=l){
int R=r>=K?K:r;
return (1ll*sum[R]-sum[l-1]+mod+qry(R+1,r,x))%mod;
}
return qsqrt(l,r);
return 0;
}
void init(){
ll i;
for(i=1;i*i*i<=m||(i-1)*(i-1)*i<m;i++) sum[i]=(sum[i-1]+qr(i)+1)%mod,K=i;
for(ll l=i,r;l<=m;l=r+1){
ll x=sqrtl(m/l);
r=m/x/x;
pr[x]=(pr[x+1]+(r-l+1)%mod*(x+1))%mod,Lb[x]=l,Rb[x]=r;
}
}
int main(){
scanf("%d%lld",&n,&m),init();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<n;i++) if(a[i]>0&&a[i+1]>0&&a[i]>m/min(a[i],a[i+1])/a[i+1]) puts("0"),exit(0);
int ans=1;
for(int i=1,j;i<=n;i++) if(a[i]==-1){
j=i;
while(j<=n&&a[j]==-1) j++;
if(j-i+(a[i-1]==0)+(a[j]==0)>=3) puts("-1"),exit(0);
ll r=qr(a[j]==0?a[i-1]:a[j]),l=qr(a[i-1]==0?a[j]:a[i-1]);
if(j-i==1) ans=(min(l,r)+1)%mod*ans%mod;
if(j-i==2) ans=1ll*ans*qry(0,l,r)%mod;
i=j;
}
printf("%d\n",ans);
}
詳細信息
File "answer.code", line 2 const int mod=998244353; ^ SyntaxError: invalid syntax