QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32055#1465. Not Our ProblemWu_RenAC ✓338ms44028kbC++141.6kb2022-05-16 20:46:112022-05-16 20:46:12

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-16 20:46:12]
  • 评测
  • 测评结果:AC
  • 用时:338ms
  • 内存:44028kb
  • [2022-05-16 20:46:11]
  • 提交

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[1000010],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: 1ms
memory: 11980kb

input:

4 100
-1 7 2 -1

output:

104

result:

ok 1 number(s): "104"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11952kb

input:

4 100
10 -1 -1 1

output:

240

result:

ok 1 number(s): "240"

Test #3:

score: 0
Accepted
time: 2ms
memory: 9864kb

input:

1 0
-1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 2ms
memory: 11832kb

input:

2 10
10 10

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 2ms
memory: 11924kb

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: 11928kb

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: 63ms
memory: 36444kb

input:

7 1000000000000000000
-1 193562447565998153 0 10833 -1 -1 12700

output:

429385005

result:

ok 1 number(s): "429385005"

Test #8:

score: 0
Accepted
time: 4ms
memory: 11884kb

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: 0ms
memory: 11968kb

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: 63ms
memory: 37284kb

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: 0
Accepted
time: 141ms
memory: 18124kb

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:

104236068

result:

ok 1 number(s): "104236068"

Test #12:

score: 0
Accepted
time: 155ms
memory: 18052kb

input:

999998 1000000
-1 538406 1 -1 -1 1 2 -1 -1 288 0 393 -1 -1 256582 0 111893 -1 1 1 -1 -1 105454 0 40 -1 -1 1 4 -1 -1 6 1 -1 -1 3 0 588226 -1 -1 2 22 -1 -1 1 477043 -1 -1 2 912 -1 -1 3 0 539669 -1 -1 1 1 -1 -1 597 0 423 -1 -1 717193 0 506800 -1 -1 424362 0 523732 -1 -1 411789 0 2 -1 -1 2 0 681371 -1 -...

output:

945384981

result:

ok 1 number(s): "945384981"

Test #13:

score: 0
Accepted
time: 338ms
memory: 41172kb

input:

999999 1000000000000000000
34 -1 -1 10403 0 945252394656439232 -1 -1 11 3 -1 -1 2789 153814328 -1 -1 685484514683924741 1 -1 -1 1 14600 -1 -1 162108378 0 942407706831037158 -1 -1 1 81 -1 -1 286801961 1 -1 -1 13177 356030442 -1 -1 9557 0 647686052355282463 -1 -1 797322887 0 33989350 -1 -1 31337243480...

output:

727350500

result:

ok 1 number(s): "727350500"

Test #14:

score: 0
Accepted
time: 2ms
memory: 11828kb

input:

50 1000
-1 -1 -1 694 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 555 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 131ms
memory: 44028kb

input:

1000000 1000000000000000000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0
Accepted
time: 2ms
memory: 11912kb

input:

50 1000
210 -1 -1 -1 -1 -1 836 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 517 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 31 -1 128 -1 -1 -1 -1

output:

0

result:

ok 1 number(s): "0"

Test #17:

score: 0
Accepted
time: 144ms
memory: 41600kb

input:

1000000 1000000000000000000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

0

result:

ok 1 number(s): "0"

Test #18:

score: 0
Accepted
time: 0ms
memory: 11880kb

input:

7 100
-1 101 0 1 -1 -1 40

output:

202

result:

ok 1 number(s): "202"

Test #19:

score: 0
Accepted
time: 1ms
memory: 12040kb

input:

17 20
2 -1 -1 2 3 -1 -1 1 3 -1 -1 21 0 5 -1 -1 1

output:

186624

result:

ok 1 number(s): "186624"

Test #20:

score: 0
Accepted
time: 5ms
memory: 12120kb

input:

8 1000000000000
5 -1 -1 2 1 -1 -1 2

output:

667440443

result:

ok 1 number(s): "667440443"

Test #21:

score: 0
Accepted
time: 5ms
memory: 12052kb

input:

4 1000000000000
5 -1 -1 2

output:

709877272

result:

ok 1 number(s): "709877272"

Test #22:

score: 0
Accepted
time: 0ms
memory: 12056kb

input:

4 1000000000000
1 -1 -1 2

output:

232569899

result:

ok 1 number(s): "232569899"