95pts求调
查看原帖
95pts求调
1209223
iris_hsd楼主2024/10/24 18:19
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;

int n, m1, m2, ans;
struct node{
    int x, y;
}a[N], b[N];

int res1[N], res2[N]; 

bool cmp(node a, node b)
{
    return a.x < b.x;
}

void solvea(int m)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > lq;
    priority_queue<int, vector<int>, greater<int> > wq;
    for(int i = 1;i <= n;i++)
    {
        wq.push(i);
    }
    for(int i = 1;i <= m;i++)
    {
        while(!lq.empty() && a[i].x > lq.top().first)
        {
            wq.push(lq.top().second);
            lq.pop();
        }
        if(wq.empty()) continue;
        int dest = wq.top();
        res1[dest]++;
        wq.pop();
        lq.push(make_pair(a[i].y, dest));
    }
    for(int i = 1;i <= n;i++)
        res1[i] += res1[i - 1];
}

void solveb(int m)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > lq;
    priority_queue<int, vector<int>, greater<int> > wq;
    for(int i = 1;i <= n;i++)
    {
        wq.push(i);
    }
    for(int i = 1;i <= m;i++)
    {
        while(!lq.empty() && b[i].x > lq.top().first)
        {
            wq.push(lq.top().second);
            lq.pop();
        }
        if(wq.empty()) continue;
        int dest = wq.top();
        res2[dest]++;
        wq.pop();
        lq.push(make_pair(b[i].y, dest));
    }
    for(int i = 1;i <= n;i++)
        res2[i] += res2[i - 1];
}

signed main()
{
    cin >> n >> m1 >> m2;
    for(int i = 1;i <= m1;i++)
        cin >> a[i].x >> a[i].y;
    for(int i = 1;i <= m2;i++)
        cin >> b[i].x >> b[i].y;
    sort(a + 1, a + m1 + 1, cmp);
    sort(b + 1, b + m2 + 1, cmp);
    solvea(m1);
    solveb(m2);
    for(int i = 1;i <= n;i++)
        ans = max(ans, res1[i] + res2[n - i]);
    cout<<ans<<"\n";
    return 0;
}
2024/10/24 18:19
加载中...