1859D - Andrey and Escape from Capygrad - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define llu unsigned long long
#define ff first
#define ss second
#define vc vector<ll>
#define vcc vector<vector<ll>>
#define vp vector<pair<ll,ll>>
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define fr(i,a,n) for(ll i=a;i<n;i++)
#define fr2(i,n,a) for(ll i=n;i>=a;i--)
#define all(x) x.begin(), x.end()
void solve()
{
    ll n;
    cin >> n;
    vcc a(n, vc(4));
    fr(i, 0, n)cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
    sort(a.begin(), a.end());
    vcc b;
    b.push_back({a[0][0], a[0][3]});
    fr(i, 1, n)
    {
        if (a[i][0] <= b[b.size() - 1][1])
        {
            b[b.size() - 1][1] = max(b[b.size() - 1][1], a[i][3]);
        }
        else b.push_back({a[i][0], a[i][3]});
    }
    vector<ll>temp;
    for (auto x : b) temp.push_back(x[0]);
    ll q;
    cin >> q;
    while (q--)
    {
        ll x;
        cin >> x;
        vc tt = {x, (ll)1e9};
        auto ind = upper_bound(all(b), tt);
        if (ind == b.begin())
        {
            cout << x << " ";
            continue;
        }
        ind--;
        if (ind == b.end())
        {
            cout << x << " ";
        }
        else cout << max(x, (*(ind))[1]) << " ";
    }
    cout << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}