比赛 20251019新安模拟赛1 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 廊桥分配 最终得分 100
用户昵称 淮淮清子 运行时间 0.789 s
代码语言 C++ 内存使用 4.48 MiB
提交时间 2025-10-19 08:59:50
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN = 1e5 + 5;
int n, m1, m2;
struct node{
    int l, r;
}f1[MAXN], f2[MAXN];
int a1[MAXN], a2[MAXN];
priority_queue<int, vector<int>, greater<int> > q;
priority_queue<pair<int, int> , vector<pair<int, int> >, greater<pair<int, int> > > p;
bool cmp(node x, node y){
    return x.l < y.l;
}

int main(){
     freopen("2021airport.in", "r", stdin);
     freopen("2021airport.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m1 >> m2;
    for(int i = 1;i <= m1;i ++) cin >> f1[i].l >> f1[i].r;
    for(int i = 1;i <= m2;i ++) cin >> f2[i].l >> f2[i].r;
    sort(f1 + 1, f1 + m1 + 1, cmp);
    sort(f2 + 1, f2 + m2 + 1, cmp);
    for(int i = 1;i <= n;i ++) q.push(i);
    for(int i = 1;i <= m1;i ++){
        while(!p.empty() && f1[i].l > p.top().first){
            q.push(p.top().second);
            p.pop();
        }
        if(!q.empty()){
            int idx = q.top(); q.pop();
            a1[idx] ++; p.push(make_pair(f1[i].r, idx));
        }
    }
    while(!q.empty()) q.pop();
    while(!p.empty()) p.pop();
    for(int i = 1;i <= n;i ++) q.push(i);
    for(int i = 1;i <= m2;i ++){
        while(!p.empty() && f2[i].l > p.top().first){
            q.push(p.top().second);
            p.pop();
        }
        if(!q.empty()){
            int idx = q.top(); q.pop();
            a2[idx] ++; p.push(make_pair(f2[i].r, idx));
        }
    }
    for(int i = 1;i <= n;i ++){
        a1[i] = a1[i - 1] + a1[i];
        a2[i] = a2[i - 1] + a2[i];
    }
    int maxx = -1;
    for(int i = 0;i <= n;i ++){
        maxx = max(maxx, a1[i] + a2[n - i]);
    }
    cout << maxx << '\n';
    return 0;
}