QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#32054 | #1465. Not Our Problem | Wu_Ren | WA | 79ms | 37928kb | C++14 | 1.6kb | 2022-05-16 20:41:43 | 2022-05-16 20:41:44 |
Judging History
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);
}
詳細信息
Test #1:
score: 100
Accepted
time: 5ms
memory: 11976kb
input:
4 100 -1 7 2 -1
output:
104
result:
ok 1 number(s): "104"
Test #2:
score: 0
Accepted
time: 0ms
memory: 11928kb
input:
4 100 10 -1 -1 1
output:
240
result:
ok 1 number(s): "240"
Test #3:
score: 0
Accepted
time: 2ms
memory: 9880kb
input:
1 0 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 11864kb
input:
2 10 10 10
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11968kb
input:
7 1000 -1 25 0 388 -1 -1 1
output:
14014
result:
ok 1 number(s): "14014"
Test #6:
score: 0
Accepted
time: 4ms
memory: 11904kb
input:
10 1000000 -1 71350 0 6 -1 2 2 -1 -1 358968
output:
652782809
result:
ok 1 number(s): "652782809"
Test #7:
score: 0
Accepted
time: 79ms
memory: 35640kb
input:
7 1000000000000000000 -1 193562447565998153 0 10833 -1 -1 12700
output:
429385005
result:
ok 1 number(s): "429385005"
Test #8:
score: 0
Accepted
time: 6ms
memory: 12000kb
input:
100 1000 -1 174 2 -1 -1 1 2 -1 -1 2 139 -1 -1 1 4 -1 -1 1 1 -1 -1 4 18 -1 -1 356 1 -1 -1 31 1 -1 -1 1 2 -1 -1 1 7 -1 -1 2 0 509 -1 -1 174 0 22 -1 -1 1 1 -1 -1 801 0 2 -1 -1 6 2 -1 -1 1 23 -1 -1 446 0 927 -1 -1 635 1 -1 -1 513 0 5 -1 -1 2 6 -1 -1 2 1 -1 -1 839 0 342 -1 -1 8 1 -1 -1 2
output:
240069117
result:
ok 1 number(s): "240069117"
Test #9:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
100 1000000 2 -1 -1 257208 1 -1 -1 80 14 -1 -1 20 113 -1 -1 2 155991 -1 -1 1 805463 -1 -1 734 1 -1 -1 942182 0 3 -1 -1 1 1 -1 -1 3 88674 -1 -1 718 0 793 -1 -1 540 1 -1 -1 1 893042 -1 -1 891 0 491 -1 -1 6 18 -1 -1 1 735332 -1 -1 1 1 -1 -1 231702 0 22 -1 -1 1 476 -1 -1 826 20 -1 -1 1 29 -1 -1 2 989 -1...
output:
279593366
result:
ok 1 number(s): "279593366"
Test #10:
score: 0
Accepted
time: 77ms
memory: 37928kb
input:
97 1000000000000000000 -1 55 1 -1 -1 844479880 0 123881535849416001 -1 -1 128083297778537531 1 -1 -1 171572811 0 352900396625380054 -1 -1 1 1 -1 -1 41 6 -1 -1 21627 155 -1 643122694 0 392322295 -1 -1 254987357 2 -1 -1 4 0 571457328786259212 -1 -1 1 8816 -1 -1 131254846109630352 0 971779784498766346 ...
output:
188490398
result:
ok 1 number(s): "188490398"
Test #11:
score: -100
Wrong Answer
time: 68ms
memory: 17972kb
input:
999998 1000 -1 343 1 -1 -1 1 3 -1 -1 1 1 -1 -1 2 0 468 -1 -1 1 1 -1 -1 783 0 5 -1 -1 2 0 760 -1 -1 318 1 -1 -1 1 320 -1 -1 27 1 -1 -1 2 2 -1 -1 2 1 -1 -1 997 1 -1 -1 547 0 313 -1 -1 4 0 304 -1 -1 1 4 -1 -1 980 0 96 -1 -1 1 797 -1 -1 13 0 13 -1 -1 19 0 401 -1 -1 1 1 -1 -1 5 5 -1 -1 26 0 458 -1 -1 6 0...
output:
0
result:
wrong answer 1st numbers differ - expected: '104236068', found: '0'