Висока будівля (Розбір)

Висока будівля#12300

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редагував:	Hasan Saleh (MathModel)

Рішення

Якщо на початку дві людини ділять один і той же поверх, то відповідь одразу НІ. В іншому випадку ми завжди можемо зробити так, щоб усі люди досягли своєї мети, починаючи з особи на найвищому поверсі, якщо тільки не існує двох людей $i, j$ , де $l_{i} \leq l_{j}$ l_i \le l_j і $r_{j} \geq r_{i}$ r_j \ge r_i.

Отже, достатньо перевірити, чи є пара $i, j$ , де $l_{i} \leq l_{j}$ l_i \le l_j і $r_{j} \geq r_{i}$ r_j \ge r_i, ми можемо це зробити, відсортувавши людей за $l_{i}$ l_i і перевіривши, чи значення $r_{i}$ r_i відсортовані.

Складність $O (n \cdot lo g (n))$ \mathcal{O}(n \cdot \log(n)).


#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll, ll>
#define lin cout << "\n";
#define mid ((l + r) / 2)
#define lc (2 * x)
#define rc (2 * x + 1)
#define double long double

using namespace std;

mt19937 rnd(time(0));

const ll N = 2e6+9;

ll n;
pll a[N];

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
            cin >> a[i].F;
        for(int i = 1 ; n>=i ; i++)
            cin >> a[i].S;
        sort(a+1,a+n+1);
        a[0]={-1e10,-1e10};
        bool g = 1;
        for(int i = 1 ; n>=i ; i++)
        {
            if(a[i].F==a[i-1].F||a[i].S<=a[i-1].S)
                g=0;
        }
        if(g)
            yes
        else
            no
    }
}