90pts求助
查看原帖
90pts求助
543206
shiroko2008楼主2022/9/3 13:05
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
priority_queue<int,vector<int>,greater<int>> q1,q2;
long long t1[400000],t2[400000],sort1[400000],sort2[400000],cnt1[200000],cnt2[200000],port1[200000],port2[200000];
bool cmp1(long long a,long long b) {
	return t1[a]<t1[b];
}
bool cmp2(long long a,long long b) {
	return t2[a]<t2[b];
}
signed main()
{
	int n,m1,m2;
	cin>>n>>m1>>m2;
	for (int i=0;i<m1;i++) {
		cin>>t1[2*i]>>t1[i*2+1];
		sort1[2*i]=2*i;
		sort1[2*i+1]=2*i+1;
	}
	for (int i=0;i<m2;i++) {
		cin>>t2[2*i]>>t2[i*2+1];
		sort2[2*i]=2*i;
		sort2[2*i+1]=2*i+1;
	}
	for (int i=0;i<n;i++) q1.push(i);
	for (int i=0;i<n;i++) q2.push(i);
	sort(sort1,sort1+2*m1,cmp1);
	sort(sort2,sort2+2*m2,cmp2);
	for (int i=0;i<m1;i++) port1[i]=150000;
	for (int i=0;i<2*m1;i++) {
		if ((sort1[i]%2)&&(port1[sort1[i]/2]!=150000)) {
			q1.push(port1[sort1[i]/2]);
			continue;
		}
		if (sort1[i]%2) continue;
		else {
			if (q1.empty()) {
				port1[i]=150000;
				continue;
			}
			port1[sort1[i]/2]=q1.top();
			cnt1[q1.top()]++;
			q1.pop();
		}
	}
	for (int i=1;i<n;i++) {
		cnt1[i]+=cnt1[i-1];
		//port[i]=150000;
	}
	for (int i=0;i<m2;i++) port2[i]=150000;
	for (int i=0;i<2*m2;i++) {
		if ((sort2[i]%2)&&(port2[sort2[i]/2]!=150000)) {
			q2.push(port2[sort2[i]/2]);
			continue;
		}
		if (sort2[i]%2) continue;
		else {
			if (q2.empty()) {
				port1[i]=150000;
				continue;
			}
			port2[sort2[i]/2]=q2.top();
			cnt2[q2.top()]++;
			//cout<<i<<' '<<q2.top()<<endl;
			q2.pop();
		}
	}
	for (int i=1;i<n;i++) cnt2[i]+=cnt2[i-1];
	int ans=0;
	for (int i=0;i<=n;i++) {
		int cur=0;
		int j=n-i;
		if (i) cur+=cnt1[i-1];
		if (j) cur+=cnt2[j-1];
		ans=max(ans,cur);
		//cout<<i<<' '<<cur<<endl;
	}
	//cout<<endl;
	/*for (int i=0;i<n;i++) cout<<cnt1[i]<<' ';
	cout<<endl;
	for (int i=0;i<n;i++) cout<<cnt2[i]<<' ';
	cout<<endl;
	for (int i=0;i<m1;i++) cout<<port1[i]<<' ';
	cout<<endl;
	for (int i=0;i<m2;i++) cout<<port2[i]<<' ';
	cout<<endl;*/
	cout<<ans<<endl;
	return 0;
}
2022/9/3 13:05
加载中...