为什么三分有80分
查看原帖
为什么三分有80分
783233
1925153zty楼主2023/11/16 21:25
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2;
const int N=1e5+6;
struct d1
{
	int l,r;
}f[N];
struct d2
{
	int l,r;
}q[N];
int ans;
int read()
{
	int ans=0;
	char c=getchar();
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9')
	ans=(ans<<1)+(ans<<3)+c-'0',c=getchar();
	return ans;
}
priority_queue<int,vector<int>,greater<int> >z1;
priority_queue<int,vector<int>,greater<int> >z2;
bool cmp(const d1&a,const d1&b)
{
	return a.l<b.l;
}
bool cmp1(const d2&a,const d2&b)
{
	return a.l<b.l;
}
void cx(int x)
{
	z1.empty();
	z2.empty();
	for(int i=1;i<=x;i++)
	z1.push(0);
	for(int i=1;i<=n-x;i++)
	z2.push(0);
	int c1=0,c2=0;
	if(x)
	for(int i=1;i<=m1;i++)
	{
		if(z1.top()<f[i].l)
		z1.pop(),z1.push(f[i].r),c1++;
	}
	if(n-x)
	for(int i=1;i<=m2;i++)
	{
		if(z2.top()<q[i].l)
		z2.pop(),z2.push(q[i].r),c2++;
	}
	cout<<max(ans,c1+c2);
	return;
}
void sf(int x,int y)
{
	int l1=x+(y-x)/3,l2=y-(y-x)/3;
	z1.empty();
	z2.empty();
	for(int i=1;i<=l1;i++)
	z1.push(0);
	for(int i=1;i<=n-l1;i++)
	z2.push(0);
	int c1=0,c2=0,e1,e2;
	if(l1)
	for(int i=1;i<=m1;i++)
	{
		if(z1.top()<f[i].l)
		z1.pop(),z1.push(f[i].r),c1++;
	}
	if(n-l1)
	for(int i=1;i<=m2;i++)
	{
		if(z2.top()<q[i].l)
		z2.pop(),z2.push(q[i].r),c2++;
	}
	e1=c1+c2;
	c1=0,c2=0;
	z1.empty();
	z2.empty();
	for(int i=1;i<=l2;i++)
	z1.push(0);
	for(int i=1;i<=n-l2;i++)
	z2.push(0);
	if(l2)
	for(int i=1;i<=m1;i++)
	{
		if(z1.top()<f[i].l)
		z1.pop(),z1.push(f[i].r),c1++;
	}
	if(n-l2)
	for(int i=1;i<=m2;i++)
	{
		if(z2.top()<q[i].l)
		z2.pop(),z2.push(q[i].r),c2++;
	}
	e2=c1+c2;
	if(e1>e2)
	{
		if(x==y-1)
		{
			cout<<e1<<endl;
			return;
		}
		else if(y-2==x)
		{
			ans=e1;
			cx(y-1);
		}
		else
		sf(x,l2);
	}
	else
	{
		if(x==y-1)
		{
			cout<<e2<<endl;
			return;
		}
		else if(y-2==x)
		{
			ans=e2;
			cx(y-1);
		}
		else
		sf(l1,y);
	}
}
int main()
{
	n=read(),m1=read(),m2=read();
	for(register int i=1;i<=m1;i++)
	f[i].l=read(),f[i].r=read();
	for(register int i=1;i<=m2;i++)
	q[i].l=read(),q[i].r=read();
	sort(f+1,f+m1+1,cmp);
	sort(q+1,q+m2+1,cmp1);
	sf(0,n);
}

record

2023/11/16 21:25
加载中...