Untitled

 avatar
domovonok
c_cpp
a year ago
1.6 kB
4
Indexable
Never
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

struct event {
    int pos, type, id;

    bool operator<(event other) const {
        if (pos != other.pos) {
            return pos < other.pos;
        } else {
            return type < other.type;
        }
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> ans(n);
    vector<event> events;
    for (int i = 0; i < n; i++) {
        int l, r, a, b;
        cin >> l >> r >> a >> b;
        events.emplace_back(l, -1, i);
        events.emplace_back(b, 1, i);
        ans[i] = b;
    }
    int q;
    cin >> q;
    vector<int> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i];
        events.emplace_back(queries[i], 0, i);
    }
    sort(events.begin(), events.end());
    reverse(events.begin(), events.end());
    multiset<int> ms;
    for (event &e : events) {
        if (e.type == -1) {
            ms.extract(ans[e.id]);
        } else if (e.type == 1) {
            if (!ms.empty()) {
                ans[e.id] = *--ms.end();
            }
            ms.insert(ans[e.id]);
        } else {
            if (!ms.empty()) {
                queries[e.id] = max(queries[e.id], *--ms.end());
            }  
        }
    }
    for (int &x : queries) {
        cout << x << ' ';
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}