Hündür Bina#12300

Hündür Bina (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Əgər başlanğıcda iki insan eyni mərtəbəni paylaşırsa, onda cavab dərhal YOX-dur. Əks halda, biz həmişə bütün insanların hədəflərinə çatmasını təmin edə bilərik, ən yüksək mərtəbədən başlayan insanla, əgər $l_{i} \leq l_{j}$ l_i \le l_j və $r_{j} \geq r_{i}$ r_j \ge r_i olan iki insan $i, j$ yoxdursa.

Beləliklə, $l_{i} \leq l_{j}$ l_i \le l_j və $r_{j} \geq r_{i}$ r_j \ge r_i olan bir cüt $i, j$ olub-olmadığını yoxlamaq kifayətdir, bunu insanlar $l_{i}$ l_i-ya əsasən sıralanaraq və $r_{i}$ r_i dəyərlərinin sıralanıb-sıralanmadığını yoxlayaraq edə bilərik.

Çətinlik $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 << "BƏLİ" << "\n";
#define no cout << "YOX" << "\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
    }
}