不明RE!
查看原帖
不明RE!
448965
杨丶老爹楼主2021/10/12 16:31

不知道为什么,一直RE

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=5e5+5;
int n,m,sum[MAXN<<3],lazy[MAXN<<3],a[MAXN*3],num;
struct node{
	int l,r,len;
}qg[MAXN];
bool cmp(node a,node b)
{
	return a.len<b.len;
}
void pushdown(int rt)
{
	if(lazy[rt])
	{
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		sum[rt<<1]+=lazy[rt];
		sum[rt<<1|1]+=lazy[rt];
		lazy[rt]=0;
		return;
	}
}
void update(int l,int r,int rt,int nowl,int nowr,int c)
{
	if(nowl<=l && nowr>=r)
	{
		sum[rt]+=c;
		lazy[rt]+=c;
		return ;
	}
	int mid=l+r>>1;
	pushdown(rt);
	if(nowl<=mid) update(l,mid,rt<<1,nowl,nowr,c);
	if(nowr>mid) update(mid+1,r,rt<<1|1,nowl,nowr,c);
	sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
int main()
{
	int x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		a[i*2]=x;a[i*2+1]=y;
		qg[i].l=x,qg[i].r=y;
		qg[i].len=y-x;
	}
	sort(a+1,a+n*2+2);
	num=unique(a+1,a+n*2+1)-(a+1);
	sort(qg+1,qg+n+1,cmp);
	int minn,maxx;
	for(int i=1;i<=n;i++)
	{
		qg[i].l=lower_bound(a+1,a+1+num,qg[i].l)-a;
		qg[i].r=lower_bound(a+1,a+1+num,qg[i].r)-a;
		minn=min(minn,qg[i].l);
		maxx=max(maxx,qg[i].r);
	}
	int head=0,tail=0;
	int ans=1e9+7;
	while(tail<n)
	{
		while(sum[1]<m && tail<=n)
		{
			tail++;
			update(minn,maxx,1,qg[tail].l,qg[tail].r,1);
		}
		if(sum[1]<m) break;
		while(sum[1]>=m && tail>=head)
		{
			head++;
			update(minn,maxx,1,qg[head].l,qg[head].r,-1);
		}
		ans=min(ans,qg[tail].len-qg[head].len);
	}
	if(ans==1e9+7) ans=-1;
	printf("%d",ans);
	return 0;
}
2021/10/12 16:31
加载中...