Csp2021 T1 corridor bridge distribution

Corridor bridge assignment

  Portal ：CSP2021 T1 Corridor bridge assignment

The main idea of the topic

  Now there is $n$ A covered bridge ,$m_1$ Domestic flights and $m_2$ International Flights . Each flight includes a time to enter the airport and a time to leave the airport . And domestic flights can only stop at the corridor bridge in the domestic area or the remote parking space , The same goes for International Flights . All planes have priority to stop on the corridor bridge .

  Now let's assign all the covered bridges to the international area and the domestic area , The total number of planes that can stop at the corridor bridge is the largest , And output the maximum value .

analysis

  We make $f[x]$ Indicates the domestic district $x$ The total number of planes that have stopped on the covered bridges ,$g[x]$ Indicates the international zone $x$ The total number of planes that have stopped on the covered bridges . So the answer is obviously ：

$$ans=\underset{i=0}{\overset{n}{\max }}\{\sum _{x=1}^{i}f[x]+\sum _{x=i}^{n-i}g[x]\}$$

  So what we need to consider now is how to quickly find $f$ and $g$ These two arrays . And it's very simple , Each time we arrange the smallest number of covered bridges to stop the arriving planes , In this way, the problem of the limitation of the number of covered bridges can be easily solved . That is to say, it is allocated to No $n$ After a corridor bridge $n+1$ It is equivalent to directly allocating to remote parking stands , No more processing is needed .

  The rest is simulation .

Code

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 100100
typedef pair<int , int> pii;                               //  The first is the departure time   The second is the number of the corridor bridge  

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0;
int m1 = 0; int m2 = 0;
struct Tplane{
    
	int l, r;
	bool operator < (const Tplane &rhs) const {
     return l < rhs.l; }
}a[MAXN], b[MAXN];
int ans1[MAXN] = {
     0 };
int ans2[MAXN] = {
     0 };

void solve(Tplane *p, int m, int *ans){
    
	priority_queue<pii, vector<pii>, greater<pii>> 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() and p[i].l >= lq.top().first)
			wq.push(lq.top().second), lq.pop();
		if(wq.empty()) continue;
		int des = wq.top(); wq.pop();
		ans[des]++;
		lq.push(make_pair(p[i].r, des)); 
	}
	for(int i = 1; i <= n; i++) ans[i] += ans[i - 1];
}

int main(){
    
	n = in; m1 = in; m2 = in; int ans = 0;
	for(int i = 1; i <= m1; i++) a[i].l = in, a[i].r = in;
	for(int i = 1; i <= m2; i++) b[i].l = in, b[i].r = in;
	sort(a + 1, a + m1 + 1); sort(b + 1, b + m2 + 1);
	solve(a, m1, ans1); solve(b, m2, ans2);
	for(int i = 0; i <= n; i++) ans = max(ans, ans1[i] + ans2[n - i]);
	cout << ans << '\n';
	return 0;
}