COCI '07 Contest 1 #5 Srednji

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

Consider a sequence A of integers, containing N integers between 1 and N. Each integer appears exactly once in the sequence.

A subsequence of A is a sequence obtained by removing some (possibly none) numbers from the beginning of A, and then from the end of A. Calculate how many different subsequences of A of odd length have their median equal to B. The median of a sequence is the element in the middle of the sequence after it is sorted. For example, the median of the sequence {5,1,3} is 3.

Input Specification

The first line contains two integers, N (1N100000) and B (1BN).

The second line contains N integers separated by spaces, the elements of sequence A.

Output Specification

Output the number of subsequences of A whose median is B.

Sample Input 1

Copy
5 4
1 2 3 4 5

Sample Output 1

Copy
2

Sample Input 2

Copy
6 3
1 2 4 5 6 3

Sample Output 2

Copy
1

Sample Input 3

Copy
7 4
5 7 2 4 3 1 6

Sample Output 3

Copy
4

Explanation for Sample Output 3

In the third example, the four subsequences of A with median 4 are {4}, {7,2,4}, {5,7,2,4,3} and {5,7,2,4,3,1,6}.


Comments


  • 0
    septence123  commented on March 13, 2017, 1:05 a.m. edit 2

    I currently have an O(N2) algorithm in Python. Is there a better time complexity in which I can solve it? or is Python just too slow for this problem?


    • 7
      Kirito  commented on March 13, 2017, 1:22 a.m.

      Since 1N105, N2 can be 1010 in a worst case, which is too slow.