1779D - Boris and His Amazing Haircut - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ull unsigned long long
#define f(i,m,n) for(int i=m; i<n;i++)
#define pii pair<int,int>
#define ff first
#define ss second
#define len(vec) (vec).size()
#define vi vector<int>
#define yup cout<<"hii"<<"\n";
#define endl "\n";
#define show(x) for(auto m:x) cout<<m<<" ";
#define all(m) (m).begin(), (m).end()
#define pb push_back
#define mp make_pair

int inf = LONG_LONG_MAX;
int mod = 1000000007;

void buildTree(int idx, int low, int high, vector<int> &seg, vector<int> &a)
{
    if (low == high)
    {
        seg[idx] = a[low];
        return;
    }
    int mid = (low + high) / 2;
    buildTree(2 * idx + 1, low, mid, seg, a);
    buildTree(2 * idx + 2, mid + 1, high, seg, a);
    seg[idx] = max(seg[2 * idx + 1], seg[2 * idx + 2]);
}

int N;

int query(int idx, int low, int high, int l, int r, vector<int> &seg)
{
    if (low>=l && high <= r)
    {
        return seg[idx];
    }
    if (l > high || r < low)
    {
        return INT_MIN;
    }
    int mid = (low + high) / 2;
    int left = query(2 * idx + 1, low, mid, l, r, seg);
    int right = query(2 * idx + 2, mid + 1, high, l, r, seg);
    return max(left, right);
}

bool solve(map<int,int> &m, map<int,vi> &mp,int i, int j, vi &seg, vi &a, vi &b)
{
    if(i>j) return true;
    if(i==j){
        if(b[i]>a[i]) return false;
        if(a[i]==b[i])  return true;
        if(m[b[i]]>0){
            m[b[i]]--;
            return true;
        }else{
            return false;
        }
    }
    int maxi=query(0,0,N-1,i,j,seg);

    bool temp = false;
    for(auto it:mp[maxi]){
        if(a[it]<b[it]){
        
        return false;}
        if(a[it]!=b[it]){
            temp = true;
        }
    }
    if(temp){
        if(m[maxi]<=0) {return false;}
        m[maxi]--;
    }
    bool ans = true;
    int prev=i-1;
    for(auto I:mp[maxi])
    {
        if(I>=i && I<=j)
        {
            ans=ans&solve(m,mp,prev+1,I-1,seg,a,b);
            prev=I;
        }
    }
    if(prev!=j)
    ans=ans&solve(m,mp,prev+1,j,seg,a,b);
    return ans;
}

void tathastu()
{
    int n;
    cin>>n;
    N= n;
    vi a(n), b(n);
    f(i,0,n)    cin>>a[i];
    f(i,0,n)    cin>>b[i];
    int m;
    cin>>m;
    vi x(m);
    f(i,0,m)    cin>>x[i];
    sort(all(x));

    vi seg(4*n);
    buildTree(0,0,n-1,seg,b);
    map<int,int> M;
    f(i,0,m)    M[x[i]]++;
    
    map<int,vector<int>> mp;
    f(i,0,n)    mp[b[i]].pb(i);

    if(solve(M,mp,0,N-1,seg,a,b))
    cout<<"YES\n";
    else
    cout<<"NO\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int testcases;
    cin>>testcases;
    for(int __=1; __<=testcases; __++)
    {
        //cout<<"Case #"<<__<<": ";
        tathastu();
    }
    return 0;
}