Untitled
c_cpp
a month ago
1.6 kB
3
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; }