Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- using namespace std;
- class MedianSubsegmentsOptimized {
- public:
- void solve() {
- int N, B;
- cin >> N >> B;
- vector<int> permutation(N);
- int pos = -1;
- for (int i = 0; i < N; ++i) {
- cin >> permutation[i];
- if (permutation[i] == B) {
- pos = i; // Записываем значения нулевых индексов
- }
- }
- // Префиксные суммы
- vector<int> prefix(N + 1, 0);
- for (int i = 0; i < N; ++i) {
- int val = 0;
- if (permutation[i] > B) {
- val = 1;
- } else if (permutation[i] < B) {
- val = -1;
- }
- prefix[i + 1] = prefix[i] + val;
- }
- // Считаем частоту префиксных сумм
- unordered_map<int, long long> freq;
- for (int i = 0; i <= pos; ++i) {
- freq[prefix[i]]++;
- }
- // Добавляем счетчик
- long long ans = 0;
- for (int j = pos + 1; j <= N; ++j) {
- ans += freq[prefix[j]];
- }
- cout << ans << "\n";
- }
- };
- int main(){
- MedianSubsegmentsOptimized solver;
- solver.solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
