95pts求调
查看原帖
95pts求调
1112642
CCCCCCnM楼主2024/10/16 19:13

灰名飞舞看不了样例,求调 错了subtask0的task9,subtask1全对

#include<bits/stdc++.h>
using namespace std;
struct airport
{
	int st,ed;
	friend bool operator < (airport z1,airport z2)
	{
		return z1.st<z2.st;
	}
} a[110005],b[110005];
struct node
{
	int ed,bg;
};
node init;
int n,m1,m2,itm,ans;
int usein[110005],useout[110005];
priority_queue<int , vector<int> , greater<int> > bge;//bridge
node stk[110007];//不会写struct的priority_queue
void solve1(int plc)
{
	if(plc==1) return;
	if(stk[plc/2].ed>stk[plc].ed)
	{
		swap(stk[plc/2],stk[plc]);
		solve1(plc/2);
	}
}
void solve2(int plc)
{
	if(stk[plc*2].ed==0) return;
	if(stk[plc*2+1].ed==0)
	{
		if(stk[plc*2].ed<stk[plc].ed)
		{
			swap(stk[plc*2],stk[plc]);
		}
		return;
	}
	int cse = stk[plc*2].ed<stk[plc*2+1].ed?plc*2:plc*2+1;
	if(stk[plc].ed<stk[cse].ed) return;
	swap(stk[plc],stk[cse]);
	solve2(cse);
	return;
}
//usein[i]国内第i个廊桥有几个飞机驶入,后做前缀和变成用i个廊桥能进入几个 
//useout类似 
int main()
{
	init.ed=0;init.bg=0;
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i = 1;i<=m1;i++) scanf("%d%d",&a[i].st,&a[i].ed);
	for(int i = 1;i<=m2;i++) scanf("%d%d",&b[i].st,&b[i].ed);
	sort(a+1,a+m1+1);
	sort(b+1,b+m2+1);
	int cm=1;
	itm = 0;
	for(int i = 1;i<=100005;i++) bge.push(i);
	while(cm<=m1)
	{
		
		if( itm==0 || stk[1].ed > a[cm].st)
		{
			usein[bge.top()] ++;
			node ld;
			ld.bg = bge.top();
			ld.ed  = a[cm].ed;
			stk[++itm] = ld;
			solve1(itm);
			bge.pop();
			cm++;
		}
		else
		{
			bge.push(stk[1].bg);
			stk[1] = stk[itm];
			stk[itm] = init;
			itm--;
			solve2(1);
		}
	}
	while(!  bge.empty()) bge.pop();
	for(int i = 0;i<=100005;i++) stk[i] = init;
	cm=1;itm=0;
	for(int i = 1;i<=100005;i++) bge.push(i);
	while(cm<=m2)
	{
		
		if( itm==0 || stk[1].ed > b[cm].st)
		{
			useout[bge.top()] ++;
			node ld;
			ld.bg = bge.top();
			ld.ed  = b[cm].ed;
			stk[++itm] = ld;
			solve1(itm);
			bge.pop();
			cm++;
		}
		else
		{
			bge.push(stk[1].bg);
			stk[1] = stk[itm];
			stk[itm] = init;
			itm--;
			solve2(1);
		}
	}
	for(int i = 1;i<=m1;i++) usein[i] += usein[i-1];
	for(int i = 1;i<=m2;i++) useout[i] += useout[i-1];
	for(int i = 0;i<=n;i++)
	{
		ans = max(ans,usein[i]+useout[n-i]);
	}
	cout<<ans;
	return 0;
}
2024/10/16 19:13
加载中...