求卡常,只需0.01s悬关
查看原帖
求卡常,只需0.01s悬关
637788
kimi0705楼主2023/10/2 13:52
#include <bits/stdc++.h>
using namespace std;
int n, m1, m2, ans;
map<int, int> M, M2;
int cnt0[100001],cnt1[100001];
struct Air{
    int l, r;
}Arr[100001];
bool cmp(Air a, Air b) {return a.l < b.l;}
int main() {
	scanf("%d%d%d", &n, &m1, &m2);
	for (int i(1); i <= m1; ++i)  scanf("%d%d", &Arr[i].l, &Arr[i].r);
    sort(Arr + 1, Arr + m1 + 1, cmp);
    for (int i(1); i <= m1; ++i) {
		if (!M.size()) M.insert({Arr[i].r, 1}), ++cnt0[1];
		else {
            int min_time, val = m1 + 1;
			for (pair<int, int> j : M) 
                if(j.first <= Arr[i].l) {
                    if(j.second < val) 
                        val = j.second, min_time = j.first;
                } else break;
			if (val != m1 + 1) M.insert({Arr[i].r, val}), M.erase(min_time), ++cnt0[M[Arr[i].r]];
			else M[Arr[i].r] = M.size() + 1, ++cnt0[M[Arr[i].r]];
		}
	}
    for (int i(1); i <= m2; ++i)  scanf("%d%d", &Arr[i].l, &Arr[i].r);
    sort(Arr + 1, Arr + m2 + 1, cmp);
    for (int i(1); i <= m2; ++i) {
		if (!M2.size()) M2.insert({Arr[i].r, 1}), ++cnt1[1];
		else {
            int min_time, val = m2 + 1;
			for (pair<int, int> j : M2) 
                if(j.first <= Arr[i].l) {
                    if(j.second < val) 
                        val = j.second, min_time = j.first;
                } else {
                    break;
                }
			if (val != m2 + 1) M2.insert({Arr[i].r, val}), M2.erase(min_time), ++cnt1[M2[Arr[i].r]];
			else M2[Arr[i].r] = M2.size() + 1, ++cnt1[M2[Arr[i].r]];
		}
	}
	for (int i(1); i <= n; ++i) cnt0[i] += cnt0[i - 1];
	for (int i(1); i <= n; ++i) cnt1[i] += cnt1[i - 1];
	for (int i(0); i <= n; ++i) ans = max(ans, cnt0[i] + cnt1[n - i]);
	printf("%d", ans);
}
2023/10/2 13:52
加载中...