#23 WA球跳,AC*39,WA*5
查看原帖
#23 WA球跳,AC*39,WA*5
724190
zhouyoyo楼主2024/10/9 20:57
#include <iostream>
#include <algorithm> 
using namespace std;

const int NR=1e5+5,MX=1e9+7,S=3e6+5;

int T[S],g[S],b[S],cnt[S],d[NR*7],dn=0,num=0,vis[NR*2],l[NR],r[NR],ansl,ansr,ans,n;;
void pushup(int p,int l,int r) { T[p]=(T[p<<1]>=T[p<<1|1])?T[p<<1]:T[p<<1|1];g[p]=(T[p<<1]>=T[p<<1|1])?g[p<<1]:g[p<<1|1]; }
void build(int x,int l,int r)
{
	if(l==r){g[x]=l;return;}
	int m=l+r>>1;
	build(x<<1,l,m); build(x<<1|1,m+1,r);  pushup(x,l,r);
}
void pushdown(int p,int l,int r) { b[p<<1]+=b[p];b[p<<1|1]+=b[p]; T[p<<1]+=b[p]; T[p<<1|1]+=b[p];b[p]=0; }
void update(int l,int r,int s,int t,int k,int p)
{
	if(l<=s&&t<=r) { T[p]+=k; b[p]+=k;  return; }
	if(b[p]&&s!=t) pushdown(p,s,t);
	int m=s+t>>1;
	if(l<=m) update(l,r,s,m,k,p<<1); if(r>m) update(l,r,m+1,t,k,p<<1|1); pushup(p,l,r);
}
struct node
{
	int x1,x2,y1,y2,id;
}a[NR*4];
bool cmp(node a,node b)
{
	return a.x1<b.x1;
}
int main()
{
	cin>>n;
	d[++dn]=0; d[++dn]=MX;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i]; d[++dn]=l[i]; d[++dn]=r[i]; if(l[i])d[++dn]=l[i]-1; d[++dn]=r[i]-1; d[++dn]=l[i]+1; d[++dn]=r[i]+1;
	}
	sort(d+1,d+dn+1);
	a[++num]=(node){0,0,1,1,0};
	int un=unique(d+1,d+dn+1)-d-1;
	for(int i=1;i<=n;i++) 
	{
		l[i]=lower_bound(d+1,d+un+1,l[i])-d; r[i]=lower_bound(d+1,d+un+1,r[i])-d;
		a[++num]=(node){1,l[i]-1,l[i]+1,r[i]-1,1}; a[++num]=(node){l[i]+1,r[i]-1,r[i]+1,dn+1,1};
		a[++num]=(node){l[i]-1,1,l[i]+1,r[i]-1,-1}; a[++num]=(node){r[i]-1,l[i]+1,r[i]+1,dn+1,-1};
	}
	build(1,1,un+1);
	sort(a+1,a+num+1,cmp);
	for(int i=1;i<=num;i++)
	{
		update(a[i].y1,a[i].y2,1,un+1,a[i].id,1);
		//update(55,55,1,un+1,0,1);
		if(T[1]>ans||(T[1]==ans&&d[g[1]]<ansr))
		{
			ans=T[1]; ansl=d[a[i].x1]; ansr=d[g[1]];
		}
	}
	if(ansl==0&&ansr==0) ansr=1;
	cout<<ansl<<' '<<ansr;
	return 0;
} 
2024/10/9 20:57
加载中...