وسيط المجلس

وسيط المجلس

الأولمبياد الوطني للبرمجة 2026 - المسابقة الرابعة، اليوم الثاني

الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت

أُعطيت تبديلة \(X\) حجمها \(N\)، تمثل ترتيب جلوس الضيوف في مجلس. التبديلة هي مصفوفة تحتوي على جميع الأعداد الصحيحة من \(1\) إلى \(N\) مرة واحدة بالضبط، حيث يمثل كل عدد رتبة أحد الضيوف.

المصفوفة الجزئية هي أي جزء متصل يمكن الحصول عليه بحذف صفر أو أكثر من العناصر من بداية التبديلة و/أو من نهايتها.

احسب عدد المصفوفات الجزئية ذات الطول الفردي التي يكون وسيطها مساويًا لـ \(M\). وسيط المصفوفة الجزئية ذات الطول الفردي هو العنصر الأوسط بعد ترتيب عناصرها تصاعديًا.

المدخلات

يحتوي السطر الأول من المدخلات على عددين صحيحين \(N\) و\(M\)، حيث \(1 \le N \le 10^5\) و\(1 \le M \le N\).

يحتوي السطر الثاني على \(N\) عددًا صحيحًا: التبديلة \(X\).

المخرجات

اطبع عددًا صحيحًا واحدًا: عدد المصفوفات الجزئية ذات الطول الفردي التي يكون وسيطها مساويًا لـ \(M\).

التقييم

المهمة الفرعية	قيود إضافية	النقاط
\(1\)	\(N \le 100\)	\(11\)
\(2\)	\(N \le 1000\)	\(12\)
\(3\)	\(N \le 5000\)	\(18\)
\(4\)	\(M = 1\) أو \(M = N\)	\(11\)
\(5\)	موضع \(M\) لا يتجاوز \(10\)	\(15\)
\(6\)	لا توجد قيود إضافية	\(33\)

أمثلة

المدخلات

5 3
1 3 2 4 5

المخرجات

3

المدخلات

5 2
2 3 4 5 1

المخرجات

1

الملاحظات

الشرح:

في حالة الاختبار الأولى، المصفوفات الجزئية الصالحة ذات الطول الفردي هي: \([3]\)، و\([1,3,2]\)، و\([3,2,4]\). جميعها وسيطها يساوي \(3\).

في حالة الاختبار الثانية، المصفوفة الجزئية الصالحة الوحيدة ذات الطول الفردي هي \([2]\). المصفوفة الجزئية \([2,3,4]\) وسيطها \(3\)، والمصفوفة الجزئية الكاملة \([2,3,4,5,1]\) وسيطها أيضًا \(3\). لذلك، توجد مصفوفة جزئية واحدة فقط ذات طول فردي وسيطها يساوي \(2\).

الحل

يجب أن تحتوي كل مصفوفة جزئية صحيحة على \(M\). استبدل كل قيمة أصغر من \(M\) بـ\(-1\) وكل قيمة أكبر منه بـ\(1\). يكون وسيط مصفوفة جزئية تحتوي \(M\) مساويًا له بالضبط عندما يصبح مجموعها صفرًا، أي عندما يتساوى عدد القيم الأصغر والأكبر. احسب كل توازن ممكن بالامتداد يسار \(M\) وخزّن تكراره، ثم امتد يمينًا؛ إذا كان توازن اليمين \(b\) فزوجه مع كل توازن أيسر \(-b\). التعقيد \(O(N)\) زمنيًا وللذاكرة.

#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';
}