You are viewing a single comment's thread. Return to all comments →
This problem can be solved by greedy in O(nlogn), which can be easily implemented.
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i) #define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i) #ifdef zerol #define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0) #else #define dbg(...) #endif void err() { cout << "\033[39;0m" << endl; } template<typename T, typename... Args> void err(T a, Args... args) { cout << a << ' '; err(args...); } // ----------------------------------------------------------------------------- const int maxn = 1E3 + 100; struct P { int s, p, tp; }; vector<P> a; int n, m; set<int> S; int main() { int x, y; cin >> n >> m; FOR (_, 0, n) { scanf("%d%d", &x, &y); a.push_back({x, y, 1}); } FOR (_, 0, m) { scanf("%d%d", &x, &y); a.push_back({x, y, 0}); } sort(a.begin(), a.end(), [](const P& a, const P& b)->bool { return a.p < b.p || (a.p == b.p && a.tp < b.tp); }); int ans = 0; for (P& u: a) { if (u.tp == 0) S.insert(u.s); else { auto it = S.upper_bound(u.s); if (it != S.end()) { ++ans; S.erase(it); } } } cout << ans << endl; }
Seems like cookies are disabled on this browser, please enable them to open this website
Real Estate Broker
You are viewing a single comment's thread. Return to all comments →
This problem can be solved by greedy in O(nlogn), which can be easily implemented.