C++(g++ 7.5.0) 解法, 执行用时: 168ms, 内存消耗: 6628K, 提交时间: 2022-08-15 22:11:10

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Node
{
    int x,y;
}a[N],b[N];
bool cmp1(Node a,Node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x>b.x;
}
bool cmp2(Node a,Node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y>b.y;
}
int n,m;
int cnt=1;
void solve()
{
    multiset<int> q;
    cin>>n>>m;
    int ans=n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=m;i++)
        cin>>b[i].x>>b[i].y;
    sort(a+1,a+1+n,cmp1);
    sort(b+1,b+1+m,cmp2);
    for(int i=1,j=1;i<=m;i++)
    {
        while(j<=n&&a[j].x>=b[i].y)
        {
            q.insert(a[j].y);
            j++;
        }
        auto it=q.upper_bound(b[i].x);
        if(it!=q.end())
        {
            q.erase(it);
        }
        else
        {
            if(q.empty())
            {
                printf("Case #%d: -1\n",cnt);
                cnt++;
                return ;
            }
            else
                ans--,q.erase(q.begin());
        }
    }
    printf("Case #%d: %d\n",cnt,ans);
    cnt++;
    return;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 122ms, 内存消耗: 6700K, 提交时间: 2023-07-12 00:18:35

#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define iofast ios::sync_with_stdio(false);cin.tie(0), cout.tie(0)
using namespace std;
const int maxn = 1e5 + 5;
pii a[maxn], b[maxn];
void solve()
{
	int n, m;
	cin >> n >> m;
	rep(i, 1, n)cin >> a[i].first >> a[i].second;
	rep(i, 1, m)cin >> b[i].second >> b[i].first;
	sort(a + 1, a + n + 1, greater<pii>());
	sort(b + 1, b + m + 1, greater<pii>());
	int j = 1;
	int ans = 0;
	multiset<int> st;
	rep(i, 1, m)
	{
		while (j <= n && a[j].first >= b[i].fi)
			st.insert(a[j++].se);
		if (st.size()>0)
		{
			auto t = st.upper_bound(b[i].se);
			if (t!=st.end()) {
				st.erase(t);
			}
			else {
				st.erase(st.begin());
				ans++;
			}
		}
		else
		{
			cout << -1 << "\n";
			return;
		}

	}
	cout << n-ans << "\n";
}
int main()
{
	iofast;
	int t;
	cin >> t;

	rep(i,1,t) {
		cout << "Case #" << i << ": ";
		solve();
	}
}