��Ŀ
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 <= N <= 40000
- 1 <= M <= N
Output
��For each case, you should output the number of consecutive sub-sequences which are the Bestcoder Sequences.
Simple input
1 1
1
5 3
4 5 3 2 1
Simple output
1
3
��Ŀ����
������������Ѱ�ڸ��������ִ�����������NΪ�����������еĸ�����������ʱ�����еġ�
˼·���Ǽ�¼����λ���ϵ��������������е�N�Ƚϵ�ʱ������������λ�õ�N��֮���ж��ٸ���N��������Ȼ��������Ѱ���ӵ��������������ټ��ϱ����������ľ��Ǵ���
AC����
8076K/265MS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include<stdio.h>
#include<map>
#include<stack>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string.h>
#include <iomanip>
#include<set>
#include<vector>
#include<functional>
#include<bitset>
using namespace std;
int a[400005];
int l[400005];
int r[400005];
int main()
{
int M,N;
while(scanf("%d%d",&M,&N)!=EOF)
{
memset(a,0,sizeof(a));
memset(l,0,sizeof(a));
memset(r,0,sizeof(a));
int gg=0,o=0,u=0;
for(int i=0; i<M; i++)
{
scanf("%d",&a[i]);
if(a[i]==N)
gg=i;
}
long long ans=0;
for(int i=gg+1; i<M; i++)
{
if(a[i]>N)r[o]=r[o-1]+1;
if(a[i]<N)r[o]=r[o-1]-1;
o++;
}
for(int i=gg-1; i>=0; i--)
{
if(a[i]>N)l[u]=l[u-1]+1;
if(a[i]<N)l[u]=l[u-1]-1;
u++;
}
multiset<int>s;
for(int i=0;i<o;i++)
s.insert(r[i]);
for(int i=0;i<u;i++)
{
ans+=s.count(-l[i]);
if(l[i]==0)
ans++;
}
ans+=s.count(0);
printf("%lld\n",ans+1);
}
}