پاسخ سوال مصاحبه با وزیران کوئرا

پاسخ سوال مصاحبه با وزیران کوئرا

در این نوشته تمرین “مصاحبه با وزیران” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال مصاحبه با وزیران کوئرا

گزارشگری از شکرستان برای گرفتن گزارش از $n$ وزیر که در مراسم جشن تولد پادشاه حضور دارند، انتخاب شده است. او روز قبل از مراسم جشن، ساعت برنامه‌ها و حضور وزیران دربار را بررسی می‌کرد. اولین چیزی که فهمید این بود که پادشاه تنها در لحظات ۱ تا m از جشن پیش وزیران می‌آید و هر یک از وزیران تنها در یک بازه‌ی زمانی مانند $[l,r]$ پادشاه را ملاقات می‌کند که ابتدا و انتهای این زمان یک عدد طبیعی است. وقتی بیش‌تر دقت کرد متوجه شد برای هر دو وزیر لحظه‌ای وجود دارد که هر دوی آن‌ها باهم با پادشاه ملاقات دارند. شب قبل از مراسم و ملاقات وزیران با پادشاه، گزارشگر متوجه می‌شود که بازه‌ی ملاقات یکی از وزیر‌ها را گم کرده است. حال می‌خواهد بداند که این بازه‌ی زمانی گم شده چند حالت مختلف می‌تواند شود.

ورودی سوال مصاحبه با وزیران

در خط اول ورودی دو عدد صحیح n و $m$ داده می‌شود که نشان‌دهنده‌ی تعداد وزیران و آخرین زمان دیدار با پادشاه است. در n – 1 خط بعدی در هر خط دو عدد طبیعی $l$ و $r$ داده می‌شود که نشان‌دهنده‌ی بازه‌ی زمانی ملاقات یک وزیر است. تضمین می‌شود که حتماً بازه‌های داده شده شرایط مساله را دارد.

$$2\le n\le 200000$$

$$1\le m\le 200000$$

$$1\le l\le r\le m$$

خروجی سوال مصاحبه با وزیران

در تنها خط خروجی یک عدد صحیح که تعداد حالت‌های مختلف برای بازه‌ی زمانی گم شده است را چاپ کنید.

حل سوال مصاحبه با وزیران

#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) 
{
    return (a.second < b.second); 
}

ll choose(ll n)
{
    return (n*n + n)/2;
}

int main()
{
    int n, m;
    cin >> n >> m;
    pair<ll, ll> baze[n-1];
    for(int i=0; i<n-1; i++) cin >> baze[i].first >> baze[i].second;
    pair<ll, ll> com = make_pair(max_element(baze, baze+n-1)->first, min_element(baze, baze+n-1, sortbysec)->second);
    ll ans = choose(m) - choose(com.first-1) - choose(m-com.second);
    cout << ans << endl;
    return 0;
}

منبع سوال: وبسایت کوئرا

اگر روش حل بهتری برای “تمرین مصاحبه با وزیران” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.