QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#231439#6625. BinariaWanXiangYun25 ✓29ms27252kbC++142.1kb2023-10-29 11:31:392023-10-29 11:31:39

Judging History

你现在查看的是最新测评结果

  • [2023-10-29 11:31:39]
  • 评测
  • 测评结果:25
  • 用时:29ms
  • 内存:27252kb
  • [2023-10-29 11:31:39]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000010
const int mod=1e6+3;
int n,m,a[N],mark[N];
int fac[N],ifac[N];
int fa[N],col[N];

int read ()
{
	int k=1,s=0;char ch=getchar ();
	while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
	while (isdigit (ch)) {s=s*10+ch-'0';ch=getchar ();}
	return k*s;
}

int Qpow (int x,int y)
{
	int res=1;
	while (y>0)
	{
		if (y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return res;
}

void Init ()
{
	n=read ();m=read ();
	fac[0]=fac[1]=1;
	for (int i=2;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	ifac[n]=Qpow (fac[n],mod-2);
	for (int i=n-1;i>=0;i--)
		ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
	for (int i=1;i<=n-m+1;i++)
		a[i]=read ();
}

int Find (int x)
{
	return x==fa[x]?x:fa[x]=Find (fa[x]);
}

int GetCol (int i)
{
	return col[Find (i)];
}

void Merge (int x,int y)
{
	int rx=Find (x),ry=Find (y);
	if (rx!=ry)
	{
		col[rx]=max (col[rx],col[ry]);
		fa[ry]=rx;
	}
}

int Calc (int n,int m)
{
	if (m>n) return 0;
	if (m==n || n==0) return 1;
	return 1ll*fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}

void Work ()
{
	for (int i=1;i<=n;i++)
	{
		fa[i]=i;
		col[i]=-1;
	}
	for (int i=2;i<=n-m+1;i++)
	{
		int j=i+m-1;
		if (a[i]-a[i-1]==1)
		{
			if (GetCol (i-1)==1)
			{
				printf ("0\n");
				return;
			}
			col[Find (i-1)]=0;
			col[Find (j)]=1;
		}
		else if (a[i]-a[i-1]==-1)
		{
			if (GetCol (i-1)==0)
			{
				printf ("0\n");
				return;
			}
			col[Find (i-1)]=1;
			col[Find (j)]=0;
		}
		else if (a[i]==a[i-1])
		{
			int colA=GetCol (i-1);
			int colB=GetCol (j);
			if (colA==-1 || colB==-1 || colA==colB)
				Merge (i-1,j);
			else
			{
				printf ("0\n");
				return;
			}
		}
		else
		{
			printf ("0\n");
			return;
		}
	}
	int cntA=0,cntB=0;
	for (int i=1;i<=m;i++)
	{
		if (i!=Find (i)) continue;
		if (col[i]==1) cntA++;
		else if (col[i]==-1) cntB++;
	}
	printf ("%d\n",Calc (cntB,a[1]-cntA));
}

signed main ()
{
	Init ();
	Work ();
	return 0;
}
/*
10 3
1 1 0 1 2 3 2 2
*/

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 1ms
memory: 11960kb

input:

1 1
0

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

1 1
1

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

10 3
1 2 2 2 2 2 2 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

10 3
1 1 0 1 2 3 2 2

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

10 3
2 2 2 2 2 2 2 2

output:

3

result:

ok 1 number(s): "3"

Test #6:

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

input:

10 3
2 1 1 1 1 2 2 3

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

input:

10 3
1 1 1 0 0 0 0 0

output:

1

result:

ok 1 number(s): "1"

Test #8:

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

input:

10 3
0 0 0 0 0 0 0 0

output:

1

result:

ok 1 number(s): "1"

Test #9:

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

input:

10 2
1 1 1 1 1 1 1 1 1

output:

2

result:

ok 1 number(s): "2"

Test #10:

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

input:

10 2
1 1 1 1 1 1 1 1 2

output:

1

result:

ok 1 number(s): "1"

Test #11:

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

input:

10 2
1 1 0 0 0 0 0 1 2

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

2 2
1

output:

2

result:

ok 1 number(s): "2"

Subtask #2:

score: 3
Accepted

Dependency #1:

100%
Accepted

Test #13:

score: 3
Accepted
time: 1ms
memory: 12016kb

input:

10 10
7

output:

120

result:

ok 1 number(s): "120"

Test #14:

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

input:

10 10
1

output:

10

result:

ok 1 number(s): "10"

Test #15:

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

input:

10 5
3 4 3 2 3 2

output:

1

result:

ok 1 number(s): "1"

Test #16:

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

input:

10 6
3 3 3 3 4

output:

10

result:

ok 1 number(s): "10"

Test #17:

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

input:

10 4
2 2 2 1 1 1 1

output:

3

result:

ok 1 number(s): "3"

Test #18:

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

input:

10 7
1 2 3 2

output:

1

result:

ok 1 number(s): "1"

Test #19:

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

input:

10 8
8 8 7

output:

1

result:

ok 1 number(s): "1"

Test #20:

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

input:

10 9
4 5

output:

70

result:

ok 1 number(s): "70"

Subtask #3:

score: 4
Accepted

Dependency #2:

100%
Accepted

Test #21:

score: 4
Accepted
time: 1ms
memory: 11968kb

input:

1000 10
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

210

result:

ok 1 number(s): "210"

Test #22:

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

input:

1000 10
5 6 6 7 7 7 7 8 7 8 7 7 7 7 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 6 6 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 6 6 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 7 7 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 6 6 6 6 ...

output:

1

result:

ok 1 number(s): "1"

Test #23:

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

input:

1000 10
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

output:

252

result:

ok 1 number(s): "252"

Test #24:

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

input:

1000 10
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 ...

output:

45

result:

ok 1 number(s): "45"

Test #25:

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

input:

1000 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...

output:

1

result:

ok 1 number(s): "1"

Test #26:

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

input:

1000 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1

result:

ok 1 number(s): "1"

Test #27:

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

input:

1000 9
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5...

output:

126

result:

ok 1 number(s): "126"

Test #28:

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

input:

1000 9
5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4...

output:

70

result:

ok 1 number(s): "70"

Test #29:

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

input:

1000 9
7 7 7 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...

output:

28

result:

ok 1 number(s): "28"

Test #30:

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

input:

1000 9
6 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...

output:

10

result:

ok 1 number(s): "10"

Test #31:

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

input:

1000 10
5 5 5 5 4 4 4 4 4 4 3 3 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

15

result:

ok 1 number(s): "15"

Test #32:

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

input:

1000 7
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

15

result:

ok 1 number(s): "15"

Test #33:

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

input:

1000 8
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5...

output:

56

result:

ok 1 number(s): "56"

Subtask #4:

score: 4
Accepted

Dependency #3:

100%
Accepted

Test #34:

score: 4
Accepted
time: 10ms
memory: 25152kb

input:

1000000 20
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9...

output:

167960

result:

ok 1 number(s): "167960"

Test #35:

score: 0
Accepted
time: 25ms
memory: 25152kb

input:

1000000 20
10 10 11 10 10 10 10 10 10 10 9 9 10 9 8 8 8 8 8 9 9 9 9 10 10 10 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 8 8 9 9 9 9 9 9 9 9 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10 10 9 10 10 10 9 9 9 9 9 9 9 9 9 9 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 1...

output:

1

result:

ok 1 number(s): "1"

Test #36:

score: 0
Accepted
time: 20ms
memory: 25260kb

input:

1000000 20
14 14 13 13 12 12 13 13 13 14 14 13 12 12 13 13 13 13 12 11 11 11 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 12 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10 10 10 10 10 11 11 11 11 11 11 11 11 11 1...

output:

1

result:

ok 1 number(s): "1"

Test #37:

score: 0
Accepted
time: 23ms
memory: 25196kb

input:

1000000 20
17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 1...

output:

153

result:

ok 1 number(s): "153"

Test #38:

score: 0
Accepted
time: 21ms
memory: 27252kb

input:

1000000 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

1

result:

ok 1 number(s): "1"

Test #39:

score: 0
Accepted
time: 9ms
memory: 25208kb

input:

1000000 20
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2...

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 24ms
memory: 25216kb

input:

1000000 20
13 13 13 13 13 13 13 12 12 12 12 12 12 13 14 14 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 12 12 12 12 12 12 12 1...

output:

5

result:

ok 1 number(s): "5"

Test #41:

score: 0
Accepted
time: 18ms
memory: 25140kb

input:

1000000 13
5 5 4 4 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

84

result:

ok 1 number(s): "84"

Test #42:

score: 0
Accepted
time: 14ms
memory: 25192kb

input:

1000000 18
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:

15

result:

ok 1 number(s): "15"

Test #43:

score: 0
Accepted
time: 20ms
memory: 25260kb

input:

1000000 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 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 #44:

score: 0
Accepted
time: 23ms
memory: 25244kb

input:

1000000 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1

result:

ok 1 number(s): "1"

Test #45:

score: 0
Accepted
time: 16ms
memory: 25332kb

input:

1000000 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1

result:

ok 1 number(s): "1"

Test #46:

score: 0
Accepted
time: 14ms
memory: 27188kb

input:

1000000 2
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 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:

2

result:

ok 1 number(s): "2"

Test #47:

score: 0
Accepted
time: 16ms
memory: 25196kb

input:

1000000 20
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...

output:

184756

result:

ok 1 number(s): "184756"

Test #48:

score: 0
Accepted
time: 19ms
memory: 25204kb

input:

1000000 20
12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1...

output:

50388

result:

ok 1 number(s): "50388"

Subtask #5:

score: 4
Accepted

Dependency #4:

100%
Accepted

Test #49:

score: 4
Accepted
time: 20ms
memory: 25264kb

input:

1000000 3000
1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 1500 15...

output:

53926

result:

ok 1 number(s): "53926"

Test #50:

score: 0
Accepted
time: 23ms
memory: 25140kb

input:

1000000 3000
1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 1990 19...

output:

375745

result:

ok 1 number(s): "375745"

Test #51:

score: 0
Accepted
time: 28ms
memory: 25148kb

input:

1000000 3000
1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1436 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 1435 14...

output:

611689

result:

ok 1 number(s): "611689"

Test #52:

score: 0
Accepted
time: 25ms
memory: 25184kb

input:

1000000 3000
1511 1512 1512 1512 1512 1511 1510 1511 1511 1512 1513 1512 1512 1511 1511 1511 1511 1510 1511 1511 1511 1512 1511 1510 1509 1510 1509 1510 1510 1509 1510 1511 1512 1512 1512 1511 1512 1511 1511 1512 1512 1513 1513 1512 1512 1513 1512 1511 1512 1511 1512 1513 1512 1512 1513 1513 1514 15...

output:

1

result:

ok 1 number(s): "1"

Test #53:

score: 0
Accepted
time: 28ms
memory: 25140kb

input:

1000000 3000
2876 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2875 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 2874 28...

output:

1

result:

ok 1 number(s): "1"

Test #54:

score: 0
Accepted
time: 19ms
memory: 25152kb

input:

1000000 3000
2977 2977 2977 2977 2977 2977 2977 2977 2977 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 2978 29...

output:

471615

result:

ok 1 number(s): "471615"

Test #55:

score: 0
Accepted
time: 27ms
memory: 25144kb

input:

1000000 3000
1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 1996 19...

output:

70180

result:

ok 1 number(s): "70180"

Test #56:

score: 0
Accepted
time: 23ms
memory: 25200kb

input:

1000000 3000
867 867 867 867 867 867 867 867 867 868 868 868 868 868 868 868 867 867 867 866 866 866 866 865 866 866 867 867 866 866 867 868 869 869 869 869 868 868 869 870 870 869 869 869 869 869 869 868 868 869 870 869 868 868 868 868 868 867 867 867 868 869 870 870 869 870 870 871 871 872 871 871...

output:

1

result:

ok 1 number(s): "1"

Test #57:

score: 0
Accepted
time: 23ms
memory: 25192kb

input:

1000000 3000
2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 2997 29...

output:

487515

result:

ok 1 number(s): "487515"

Test #58:

score: 0
Accepted
time: 28ms
memory: 25196kb

input:

1000000 3000
2397 2397 2397 2397 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2396 2397 2397 2397 2397 2397 2397 2397 2397 2396 2396 2396 2396 2397 2397 2397 2397 2397 2397 2398 2398 2398 2398 23...

output:

943965

result:

ok 1 number(s): "943965"

Test #59:

score: 0
Accepted
time: 19ms
memory: 25212kb

input:

1000000 1337
478 477 477 477 477 478 478 478 479 480 480 479 478 477 477 477 477 477 478 478 478 479 478 478 477 477 477 477 478 478 479 479 479 479 479 480 479 479 478 479 480 480 480 481 482 482 482 482 482 482 482 481 481 480 480 479 479 480 481 481 481 481 482 482 482 483 483 483 484 484 485 484...

output:

645202

result:

ok 1 number(s): "645202"

Subtask #6:

score: 7
Accepted

Dependency #5:

100%
Accepted

Test #60:

score: 7
Accepted
time: 9ms
memory: 22500kb

input:

1000000 1000000
500000

output:

375001

result:

ok 1 number(s): "375001"

Test #61:

score: 0
Accepted
time: 10ms
memory: 22220kb

input:

1000000 1000000
376577

output:

529387

result:

ok 1 number(s): "529387"

Test #62:

score: 0
Accepted
time: 8ms
memory: 21740kb

input:

1000000 999999
876543 876543

output:

614361

result:

ok 1 number(s): "614361"

Test #63:

score: 0
Accepted
time: 10ms
memory: 22724kb

input:

1000000 999999
553875 553876

output:

277031

result:

ok 1 number(s): "277031"

Test #64:

score: 0
Accepted
time: 13ms
memory: 23836kb

input:

1000000 500000
364645 364645 364645 364645 364645 364645 364645 364644 364644 364644 364644 364644 364644 364644 364643 364643 364643 364643 364643 364643 364643 364643 364643 364643 364643 364643 364642 364642 364642 364642 364642 364642 364642 364642 364642 364642 364642 364642 364642 364642 36464...

output:

48211

result:

ok 1 number(s): "48211"

Test #65:

score: 0
Accepted
time: 16ms
memory: 23016kb

input:

1000000 654321
306156 306156 306156 306156 306156 306156 306156 306156 306156 306156 306156 306157 306157 306157 306157 306157 306157 306157 306157 306157 306158 306158 306158 306158 306158 306158 306158 306158 306157 306157 306157 306157 306157 306157 306157 306157 306157 306157 306157 306157 30615...

output:

149704

result:

ok 1 number(s): "149704"

Test #66:

score: 0
Accepted
time: 29ms
memory: 24992kb

input:

1000000 200000
134176 134176 134177 134177 134178 134178 134177 134178 134178 134178 134178 134177 134177 134178 134179 134179 134179 134179 134179 134179 134179 134179 134179 134179 134178 134179 134179 134179 134179 134178 134178 134178 134178 134177 134177 134177 134177 134177 134176 134176 13417...

output:

814377

result:

ok 1 number(s): "814377"

Test #67:

score: 0
Accepted
time: 11ms
memory: 22704kb

input:

1000000 909090
9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 9045 ...

output:

604727

result:

ok 1 number(s): "604727"

Test #68:

score: 0
Accepted
time: 9ms
memory: 23464kb

input:

1000000 1000000
1000000

output:

1

result:

ok 1 number(s): "1"

Test #69:

score: 0
Accepted
time: 8ms
memory: 21908kb

input:

1000000 1000000
0

output:

1

result:

ok 1 number(s): "1"

Test #70:

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

input:

1000000 999999
499999 500000

output:

507814

result:

ok 1 number(s): "507814"

Extra Test:

score: 0
Extra Test Passed