Majlis Median
Time limit: 1 s.
Memory limit: 256 MB
You are given a permutation \(X\) of size \(N\), representing the seating order of guests in a Majlis. The permutation is an array that contains all integers from \(1\) to \(N\) exactly once, where each integer represents a guest’s rank.
A subarray is any contiguous segment obtained by removing zero or more elements from the beginning and/or the end of the permutation.
Count how many subarrays of odd length have median equal to \(M\). The median of an odd-length subarray is the middle element after sorting the subarray.
Input
The first line of input contains two integers \(N\) and \(M\) (\(1 \leq N \leq 10^5\), \(1 \leq M \leq N\)).
The second line contains \(N\) integers - the permutation \(X\).
Output
Print a single integer - the number of odd-length subarrays whose median is equal to \(M\).
Scoring
| Subtask | Additional constraints | Points |
|---|---|---|
| \(1\) | \(N \le 100\) | \(11\) |
| \(2\) | \(N \le 1000\) | \(12\) |
| \(3\) | \(N \le 5000\) | \(18\) |
| \(4\) | \(M = 1\) or \(M = N\) | \(11\) |
| \(5\) | The position of \(M\) is at most \(10\) | \(15\) |
| \(6\) | no additional constraints | \(33\) |
Examples
Input
5 3
1 3 2 4 5
Output
3
Input
5 2
2 3 4 5 1
Output
1
Note
Explanation:
In the first sample test case, valid odd-length subarrays are: [3], [3, 2, 4] and [1, 3, 2, 4, 5] . All have median equal to 3.
In the second sample test case, the only valid odd-length subarray is [2]. The subarray [2, 3, 4] has median 3, and the full subarray: [2, 3, 4, 5, 1] also has median 3. Therefore, only one odd-length subarray has median equal to 2.
Solution
Every valid subarray must contain \(M\). Replace each value smaller than \(M\) by \(-1\) and each value greater than \(M\) by \(1\).
For a subarray containing \(M\), its median is \(M\) exactly when its sum after this replacement is zero: it then contains equally many smaller and greater values.
Starting next to \(M\), calculate every balance obtainable by extending to the left and store its frequency. Then extend to the right. If the right balance is \(b\), it can be paired with any left balance \(-b\).
The complexity is \(O(N)\) time and memory.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, median;
cin >> n >> median;
vector<int> permutation(n);
int position = 0;
for (int i = 0; i < n; i++) {
cin >> permutation[i];
if (permutation[i] == median) {
position = i;
}
}
vector<int> frequency(2 * n + 1, 0);
int offset = n;
int balance = 0;
frequency[offset] = 1;
for (int i = position - 1; i >= 0; i--) {
balance += (permutation[i] > median ? 1 : -1);
frequency[offset + balance]++;
}
long long answer = 0;
balance = 0;
for (int i = position; i < n; i++) {
if (i > position) {
balance += (permutation[i] > median ? 1 : -1);
}
answer += frequency[offset - balance];
}
cout << answer << '\n';
}