[CSP-S 2021] 廊桥分配

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m1,m2,f[N],g[N],ans;//f国内 g国际
using pii=pair<int,int>;
pii a[N],b[N];
void calc(pii p[],int m,int res[]){
    priority_queue<int,vector<int>,greater<int> >free;  // 空闲廊桥
    priority_queue<pii,vector<pii>,greater<pii> >busy;  // 使用中廊桥 first:离开时间 second:编号
    for(int i=1;i<=n;i++) free.push(i);
    int cnt[N]={0};
    for(int i=1;i<=m;i++){
        int arr=p[i].first;int dep=p[i].second;
        while(!busy.empty()&&busy.top().first<arr){  // 释放已离开的廊桥
            free.push(busy.top().second);
            busy.pop();
        }
        if(free.empty()) continue;  // 无空闲，去远机位
        int id=free.top();free.pop();
        cnt[id]++;
        busy.push({dep,id});
    }
    res[0]=0;
    for (int i=1;i<=n;i++) res[i]=res[i-1]+cnt[i];  // 前缀和
}
int main(){
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++) cin>>a[i].first>>a[i].second;
    for(int i=1;i<=m2;i++) cin>>b[i].first>>b[i].second;
    sort(a+1,a+m1+1);
    sort(b+1,b+m2+1);
    calc(a,m1,f);
    calc(b,m2,g);
    for(int i=0;i<=n;i++) ans=max(ans,f[i]+g[n-i]);  // 枚举分配方案
    cout<<ans;
    return 0;
}