تغطية المهرجان

تغطية المهرجان

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

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

أثناء مهرجان كبير في السعودية، ينظم فارس وعبدالعزيز الخدمات على طول طريق طويل جدًا.

توجد عدة فرق خدمية. يصبح كل فريق متاحًا في وقت معين، وعندها تصبح الفترة المخصصة له على الطريق فعالة ويمكنها خدمة كل الموجودين داخلها. وتوجد نقاط مستهدفة مهمة يجب خدمتها جميعًا.

لكل فريق تُعطى المعلومات التالية:

• وقت تفعيله؛
• الطرف الأيسر لفترته؛
• الطرف الأيمن لفترته.

عند الزمن \(T\) تكون الفترة فعالة إذا كان الفريق قد أصبح متاحًا عند \(T\) أو قبله. وتغطي الفترة \([l_i,r_i]\) النقطة \(x\) إذا كان \(l_i\le x\le r_i\)، والطرفان مشمولان.

أوجد أصغر زمن تكون فيه كل النقاط المستهدفة مغطاة بفترة فعالة واحدة على الأقل. إذا استحال ذلك فاطبع \(-1\).

المدخلات

يحتوي السطر الأول على \(n\) و\(m\)، عدد الفترات وعدد النقاط. يحتوي كل من الأسطر \(n\) التالية على \(t_i,l_i,r_i\). ويحتوي السطر الأخير على النقاط \(x_1,x_2,\ldots,x_m\).

مضمون أن:

• \(1\le n,m\le2\cdot10^5\)؛
• \(1\le t_i\le10^9\)؛
• \(-10^9\le l_i<r_i\le10^9\)؛
• \(-10^9\le x_i\le10^9\).

المخرجات

اطبع أقل زمن تصبح فيه كل النقاط مغطاة، أو \(-1\) إذا كان ذلك مستحيلًا.

التقييم

المهمة الفرعية	القيود الإضافية	النقاط
\(1\)	\(1\le n,m\le200\)	\(14\)
\(2\)	كل الفترات تتفعّل في الوقت نفسه	\(13\)
\(3\)	النقاط هي \(1,2,\ldots,m\) و\(n,m\le5000\)	\(11\)
\(4\)	النقاط هي \(1,2,\ldots,m\)	\(13\)
\(5\)	لا تتداخل فترتان و\(n,m\le5000\)	\(17\)
\(6\)	لا تتداخل فترتان	\(15\)
\(7\)	لا توجد قيود إضافية	\(17\)

أمثلة

المدخلات

4 5
3 1 4
1 6 8
5 2 7
2 9 10
2 3 6 7 10

المخرجات

3

المدخلات

3 4
2 1 3
5 6 8
7 10 12
2 4 7 11

المخرجات

-1

ملاحظات

ملاحظات المثال الأول:

عند الزمن \(T\) تكون الفترة فعالة إذا كان \(t_i\le T\). وتكون النقطة \(x\) مغطاة إذا وُجدت فترة فعالة \([l_i,r_i]\) تحقق \(l_i\le x\le r_i\).

النقاط المستهدفة في المثال الأول هي \(2,3,6,7,10\).

• عند الزمن \(1\)، تكون الفترة \([6,8]\) وحدها فعالة.
  • النقطتان \(2\) و\(3\) غير مغطاتين.
  • النقطتان \(6\) و\(7\) مغطاتان بالفترة \([6,8]\).
  • النقطة \(10\) غير مغطاة.
• عند الزمن \(2\)، تكون الفترتان \([6,8]\) و\([9,10]\) فعالتين.
  • النقطتان \(2\) و\(3\) غير مغطاتين.
  • النقطتان \(6\) و\(7\) مغطاتان بالفترة \([6,8]\).
  • النقطة \(10\) مغطاة بالفترة \([9,10]\).
• عند الزمن \(3\)، تكون الفترات \([1,4]\) و\([6,8]\) و\([9,10]\) فعالة.
  • النقطتان \(2\) و\(3\) مغطاتان بالفترة \([1,4]\).
  • النقطتان \(6\) و\(7\) مغطاتان بالفترة \([6,8]\).
  • النقطة \(10\) مغطاة بالفترة \([9,10]\).

لذلك، إجابة المثال الأول هي \(3\).

ملاحظات المثال الثاني:

النقاط المستهدفة في المثال الثاني هي \(2,4,7,11\).

• عند الزمن \(2\)، تكون الفترة \([1,3]\) وحدها فعالة.
  • النقطة \(2\) مغطاة، بينما النقاط \(4\) و\(7\) و\(11\) غير مغطاة.
• عند الزمن \(5\)، تكون الفترتان \([1,3]\) و\([6,8]\) فعالتين.
  • النقطتان \(2\) و\(7\) مغطاتان، بينما \(4\) و\(11\) غير مغطاتين.
• عند الزمن \(7\)، تكون الفترات \([1,3]\) و\([6,8]\) و\([10,12]\) فعالة.
  • النقاط \(2\) و\(7\) و\(11\) مغطاة، لكن النقطة \(4\) تظل غير مغطاة.

لا تغطي أي فترة النقطة \(4\)، لذلك لا يوجد زمن تكون فيه جميع النقاط مغطاة، وإجابة المثال الثاني هي \(-1\).

قد تتداخل الفترات، وقد تتكرر النقاط المستهدفة.

الحل

لكل نقطة \(x\) نحتاج أصغر وقت تفعيل بين الفترات التي تحتويها، والإجابة أكبر هذه الأوقات على جميع النقاط. رتّب الفترات بحسب طرفها الأيسر والنقاط بحسب موضعها، وامسح من اليسار إلى اليمين. قبل معالجة \(x\) أضف كل فترة تحقق \(l_i\le x\) إلى طابور أولوية مرتب بوقت التفعيل، واحذف من قمته الفترات التي صار طرفها الأيمن أصغر من \(x\). تصبح القمة أبكر فترة تغطي \(x\)، وإذا فرغ الطابور استحال تغطية النقطة. التعقيد \(O((N+M)\log N)\) زمنيًا و\(O(N+M)\) للذاكرة.

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

struct Interval {
    long long time;
    long long left;
    long long right;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Interval> intervals(n);
    for (Interval& interval : intervals) {
        cin >> interval.time >> interval.left >> interval.right;
    }

    vector<long long> targets(m);
    for (long long& x : targets) {
        cin >> x;
    }

    sort(intervals.begin(), intervals.end(),
        [](const Interval& a, const Interval& b) {
            return a.left < b.left;
        });
    sort(targets.begin(), targets.end());

    priority_queue<
        pair<long long, long long>,
        vector<pair<long long, long long>>,
        greater<pair<long long, long long>>
    > active;

    int nextInterval = 0;
    long long answer = 0;

    for (long long x : targets) {
        while (nextInterval < n && intervals[nextInterval].left <= x) {
            active.push( {
                intervals[nextInterval].time,
                intervals[nextInterval].right
            });
            nextInterval++;
        }

        while (!active.empty() && active.top().second < x) {
            active.pop();
        }

        if (active.empty()) {
            cout << -1 << '\n';
            return 0;
        }

        answer = max(answer, active.top().first);
    }

    cout << answer << '\n';
}