HDU 4908

BestCoder Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 113 Accepted Submission(s): 49

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 as Bestcoder Sequence. As the best coder, Mr potato has strong curiosity, he wonder the number of consecutive sub-sequences which are bestcoder 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 the Bestcoder 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

在一个1-N的全排列中。 找有多少个子串，这个子串的中位数是M, 这个串必须跨越M的位置。 然后需要大于M的个数等于小于M的个数。 一边统计，一边直接搞就可以了。

/* ***
Author :kuangbin
Created Time :2014/8/3 19:07:52
File Name :B.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const int MAXN = 40010;

int a[MAXN];
int n,m;
int num[MAXN*2];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
while(scanf(“%d%d”,&n,&m) == 2)
{
int id = -1;
for(int i = 1;i <= n;i++)
{
scanf(“%d”,&a[i]);
if(a[i] == m)
id = i;
}
memset(num,0,sizeof(num));
int s = 0;
for(int i = id;i >= 1;i–)
{
if(a[i] > m)s++;
else if(a[i] < m)s–;
num[s+40000]++;
}
int ans = 0;
s = 0;
for(int i = id;i <= n;i++)
{
if(a[i] < m)s++;
else if(a[i] > m)s–;
ans += num[40000+s];
}
printf(“%d\n”,ans);
}
return 0;
}