不会用stl的憨憨打出了屎山代码
查看原帖
不会用stl的憨憨打出了屎山代码
222889
summer_summer楼主2021/10/25 19:32
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (10000000)
const int N=100010;
ll n,m1,m2;
ll ans1[N],ans2[N];//ans[i]表示使第i架飞机停在廊桥上需要的最少廊桥数量 
int cnt1[N],cnt2[N];//桶 
struct Node
{
	ll st,ed;
	int num;
}pl1[N<<1],pl2[N<<1];
struct Node1
{
	ll l,r,sum;
};
struct Tree//线段树 
{
	Node1 tr[N<<3];
	void clear()
	{
		memset(tr,0,sizeof(tr));
	}
	void build(int x,int L,int R)
	{
		tr[x].l=L,tr[x].r=R,tr[x].sum=0;
		if(L==R) return;
		int mid=(L+R)>>1;
		build(x*2,L,mid);
		build(x*2+1,mid+1,R);
	}
	void add_point(int now,int x,int k)
	{
		if(x<tr[now].l||x>tr[now].r) return;
		if(tr[now].l==tr[now].r&&tr[now].l==x)
		{
			tr[now].sum+=k;
			return;
		}
		int mid=(tr[now].l+tr[now].r)>>1;
		if(x<=mid) add_point(now*2,x,k);
		if(x>mid) add_point(now*2+1,x,k);
		tr[now].sum=tr[now*2].sum+tr[now*2+1].sum;
	}
	ll find(int now,ll sum1)//二分,找到最小的x使得cnt的前x前缀和小于x,x就是ans[i] 
	{
//		cout<<"tree now:"<<now<<" "<<tr[now].sum<<" "<<sum1<<endl;//
		if(tr[now].l==tr[now].r)
		{
			if(sum1+tr[now].sum<tr[now].r) return tr[now].r;
			return 0x7fffffff;
		}
		if(sum1+tr[now*2].sum<tr[now*2].r) return min(find(now*2,sum1),tr[now*2].r);
		else if(sum1+tr[now].sum<tr[now].r) return min(find(now*2+1,sum1+tr[now*2].sum),tr[now].r);
		return 0x7fffffff;
	}
}sg_tr;
struct Heap//小根堆 
{
	Node pl[N];
	int h;
	void up(int x)
	{
		if(x==1) return;
		if(pl[x].ed<pl[x/2].ed)
		{
			swap(pl[x],pl[x/2]);
			up(x/2);
		}
	}
	void down(int x)
	{
		int son=x*2;
		if(x*2+1<=h&&pl[son].ed>pl[x*2+1].ed) son=x*2+1;
		if(son<=h&&pl[son].ed<pl[x].ed)
		{
			swap(pl[son],pl[x]);
			down(son);
		}
	}
	void push(Node x)
	{
		pl[++h]=x;
		up(h);
	}
	void pop()
	{
		if(h==0) return;
		swap(pl[h],pl[1]);
		h--;
		down(1);
	}
	Node top()
	{
		return pl[1];
	}
	int size()
	{
		return h;
	}
}q;
ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch==-1) return x*f;
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
bool cmp(Node a,Node b)
{
	if(a.st!=b.st) return a.st<b.st;
	return a.ed<b.ed;
}
void hs1()
{
	sg_tr.clear();
	sg_tr.build(1,1,m1);
//	cout<<"start:"<<endl;//
	for(int i=1;i<=m1;i++)
	{
		pl1[i].num=i;
		while(q.size()&&q.top().ed<pl1[i].st)
		{
			sg_tr.add_point(1,ans1[q.top().num],-1);
			q.pop();
		}
		ans1[i]=sg_tr.find(1,0);
		sg_tr.add_point(1,ans1[i],1);
//		cout<<"num:"<<i<<" "<<pl1[i].st<<" "<<pl1[i].ed<<" "<<ans1[i]<<endl;//
		q.push(pl1[i]);
	}
}
int main()
{
//	freopen("airport.in","r",stdin);
//	freopen("airport.out","w",stdout);
	n=read();
	m1=read();
	m2=read();//没有判m1+m2<n,CCF我求您做个人 
	for(int i=1;i<=m1;i++)
	{
		pl1[i].st=read();
		pl1[i].ed=read();
	}
	for(int i=1;i<=m2;i++)
	{
		pl2[i].st=read();
		pl2[i].ed=read();
	}
	sort(pl1+1,pl1+1+m1,cmp);
	sort(pl2+1,pl2+1+m2,cmp);
	hs1();
	swap(m1,m2);
	swap(pl1,pl2);
	swap(ans1,ans2);
	q.h=0;
	hs1();
	for(int i=1;i<=m1;i++)
	{
		cnt1[ans1[i]]++;
	}
	for(int i=1;i<=m2;i++)
	{
		cnt2[ans2[i]]++;
	}
	for(int i=1;i<=m1;i++)
	{
		cnt1[i]+=cnt1[i-1];
	}
	for(int i=1;i<=m2;i++)
	{
		cnt2[i]+=cnt2[i-1];
	}
	int Max=0x80000000;
	for(int i=0;i<=n;i++)
	{
		Max=max(Max,cnt1[i]+cnt2[n-i]);
	}
	cout<<Max<<endl;
	return 0;
}
//rp++
2021/10/25 19:32
加载中...