الموضع الأمثل

الموضع الأمثل

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

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

يُمثَّل الطريق بخط الأعداد الصحيحة.

تستقبل المملكة سلسلة من الطلبات. يُضيف كل طلب مقطعًا مغلقًا جديدًا \([l, r]\) على الطريق. تمثل هذه المقاطع مناطق محظورة.

بعد إضافة كل مقطع جديد، يجب عليك اختيار موضع صحيح \(x\) على الطريق.

تُعرَّف المسافة بين نقطة \(x\) ومقطع \([l, r]\) كما يلي:

\(\mathrm{dist}(x, [l, r]) = \begin{cases} 0 & \text{if } l \le x \le r \\ l - x & \text{if } x < l \\ x - r & \text{if } x > r \end{cases}\)

بعبارة أخرى، تكون المسافة \(0\) إذا كانت النقطة داخل المقطع، وإلا فهي المسافة إلى أقرب طرف من أطرافه.

لنقطة ثابتة \(x\)، تُعرَّف نتيجتها بأنها أكبر مسافة من \(x\) إلى أي مقطع تمت إضافته حتى الآن.

مهمتك هي اختيار العدد الصحيح \(x\) الذي يُصغّر هذه النتيجة بعد كل تحديث. إذا كان هناك أكثر من اختيار أمثل، فاطبع الأصغر منها.

المدخلات

يحتوي السطر الأول على عدد صحيح واحد \(Q\)، حيث \(1 \le Q \le 2 \cdot 10^5\).

يحتوي كل سطر من الأسطر \(Q\) التالية على عددين صحيحين \(l_i\) و\(r_i\)، حيث \(1 \le l_i \le r_i \le 10^9\).

المخرجات

لكل استعلام، اطبع عددًا صحيحًا واحدًا يمثل أفضل موضع بعد معالجة ذلك الاستعلام.

التقييم

تتكون المسألة من عدة مهام جزئية. لكل مهمة جزئية قيود إضافية وعدد محدد من النقاط.

المهمة الفرعية	قيود إضافية	النقاط
\(1\)	\(l_i = 1\)	\(23\)
\(2\)	\(Q, l_i, r_i \le 200\)	\(25\)
\(3\)	\(l_i = r_i\)	\(32\)
\(4\)	لا توجد قيود إضافية	\(20\)

المجموع الكلي للنقاط هو \(100\) نقطة.

أمثلة

المدخلات

4
3 5
7 9
2 4
5 9

المخرجات

3
6
5
5

المدخلات

3
1 4
1 1
1 2

المخرجات

1
1
1

الملاحظات

في المثال الأول:

• بعد التحديث الأول: تتم إضافة المقطع \([3,5]\)

المقاطع الحالية: \([3,5]\)

نختار نقطة \(x\) تُصغّر أكبر مسافة إلى \([3,5]\).

أي نقطة داخل \([3,5]\) تكون مسافتها إلى المقطع تساوي \(0\). الاختيار الأفضل هو \(x = 3\) (أصغر نقطة مثلى).

الإجابة: \(3\)

• بعد التحديث الثاني: تتم إضافة المقطع \([7,9]\) فتصبح المقاطع \([3,5], [7,9]\)

نختار الآن \(x\) التي تُصغّر أكبر مسافة إلى كلا المقطعين.

أفضل نقطة تقع بينهما. بفحص المرشحين، نجد أن \(x = 6\) يوازن المسافة بين المقطعين.

الإجابة: \(6\)

• بعد التحديث الثالث: تتم إضافة المقطع \([2,4]\) فتصبح المقاطع \([2,4], [3,5], [7,9]\)

أصبحت المقاطع الآن أقرب إلى اليسار. تنزاح النقطة المثلى نحو اليسار، ويصبح الاختيار الأفضل هو \(x = 5\).

الإجابة: \(5\)

• بعد التحديث الرابع: تتم إضافة المقطع \([5,9]\) فتصبح المقاطع \([2,4], [3,5], [5,9], [7,9]\)

أصبحت المقاطع متداخلة بشكل كبير على اليمين. يظل أفضل موضع هو \(x = 5\).

الإجابة: \(5\)

الحل

لا يهم إلا طرفان: \(L\) أكبر طرف أيسر، و\(R\) أصغر طرف أيمن. إذا كان \(L\le R\) فكل نقطة في \([L,R]\) تقع في جميع المقاطع، وأصغر موضع أمثل هو \(L\). وإلا فالنتيجة \(\max(L-x,x-R)\) وتبلغ حدها الأدنى عند منتصف \(R\) و\(L\)؛ وعند وجود عددين صحيحين مثاليين تختار القسمة الصحيحة الأصغر. حدّث \(L\) و\(R\) بعد كل عملية. التعقيد \(O(Q)\) زمنيًا و\(O(1)\) للذاكرة.

#include <algorithm>
#include <iostream>
#include <limits>
using namespace std;

int main() {
    int q;
    cin >> q;

    long long maximumLeft = numeric_limits<long long>::min();
    long long minimumRight = numeric_limits<long long>::max();

    while (q--) {
        long long left, right;
        cin >> left >> right;

        maximumLeft = max(maximumLeft, left);
        minimumRight = min(minimumRight, right);

        if (maximumLeft <= minimumRight) {
            cout << maximumLeft << '\n';
        } else {
            cout << (maximumLeft + minimumRight) / 2 << '\n';
        }
    }
}