BestCoder Sequence

Problem Description

Mr Potato is a coder.
Mr Potato is the BestCoder.

One night, an amazing sequence appeared in his dream. Length of this sequence is odd, the median number is M, and he named this sequence asBestcoder Sequence.

As the best coder, Mr potato has strong curiosity, he wonder the number of consecutive sub-sequences which arebestcoder sequences in a given permutation of 1 ~ N.

 

Input

Input contains multiple test cases.
For each test case, there is a pair of integers N and M in the first line, and an permutation of 1 ~ N in the second line.

[Technical Specification]
1. 1 <= N <= 40000
2. 1 <= M <= N

 

Output

For each case, you should output the number of consecutive sub-sequences which are theBestcoder Sequences.

 

Sample Input

1 1
1
5 3
4 5 3 2 1

 

Sample Output

1
3

Hint
For the second case, {3},{5,3,2},{4,5,3,2,1} are Bestcoder Sequence.
 

 

Source

BestCoder Round #3

 

Recommend

We have carefully selected several similar problems for you:  4910 4909 4906 4904 4903 

题意：给定N和M，N为序列的长度。由1~N组成。求有多少连续的子序列是以M为中位数，且长度为奇数。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define mid 40000
#define MAXN 100017
int dp[MAXN], num[MAXN];
void init()
{
	memset(dp,0,sizeof(dp));
	memset(num,0,sizeof(num));
}
int main()
{
	int n, m;
	int i, j;
	while(~scanf("%d%d",&n,&m))
	{
		init();
		int t = 0;
		for(i = 1; i <= n; i++)
		{
			scanf("%d",&num[i]);
			if(num[i] == m)//记录m位置
				t = i;
		}
		int cont = 0;
		for(i = t+1; i <= n; i++)
		{
			if(num[i] > m)//大的加
				cont++;
			else		  //小的减
				cont--;
			dp[cont+mid]++;//记录出现该状态的次数
		}
		cont = ++dp[mid];//当状态数为mid。才满足中位数
		int tt = 0;
		for(i = t-1; i >= 1; i--)
		{
			if(num[i] > m)
				tt++;
			else
				tt--;
			cont+=dp[-tt+mid];//状态相加为mid的个数
		}
		printf("%d\n",cont);
	}
	return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN  50000
using namespace std;
int num[MAXN+10],sum[MAXN+10],a[MAXN+10+MAXN];
int main()
{
    int M,N,M_id;
    while (scanf("%d %d",&N,&M)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        memset(num,0,sizeof(num));
        num[0]=sum[0]=0;
        for (int i=1;i<=N;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            if (tmp>M) num[i]=1;
            else if (tmp==M) num[i]=0,M_id=i;
            else num[i]=-1;
            sum[i]=sum[i-1]+num[i];
        }
        int cnt=0;
        for (int j=0;j<=M_id-1;j++)
            a[sum[j]+MAXN]++;
        for (int i=M_id;i<=N;i++)
            cnt+=a[sum[i]+MAXN];
        printf("%d\n",cnt);
    }
    return 0;
}