社区讨论

为什么我要开16倍?

P1712[NOI2016] 区间参与者 4已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo7xswmq
此快照首次捕获于
2023/10/27 09:31
2 年前
此快照最后确认于
2023/10/27 09:31
2 年前
查看原帖
RT,我虽然AC了,按道理来说,我不应该只要开 88 倍的吗,但是我开了 1616 倍才AC啊为什么为什么
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
			ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0) {
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
const int N=5e5+5,INF=0x3f3f3f3f;
int mx[N<<4],d[N<<4],c[N<<1];
int n,m,g,ans=INF,l=1,r=0;
map<int,int>mp;
struct Node {
	int l,r,len;
}a[N];
inline bool cmp(Node x,Node y) {
	return x.len<y.len;
}
inline void update(int k,int v) {
	d[k]+=v;
	mx[k]+=v;
}
inline void pd(int k) {
	if(!d[k])
		return;
	update(k<<1,d[k]);
	update(k<<1|1,d[k]);
	d[k]=0;
}
void modify(int k,int l,int r,int x,int y,int v) {
	if(x<=l&&r<=y)
		return update(k,v);
	pd(k);
	int mid=(l+r)/2;
	if(x<=mid)
		modify(k<<1,l,mid,x,y,v);
	if(mid<y)
		modify(k<<1|1,mid+1,r,x,y,v);
	mx[k]=max(mx[k<<1],mx[k<<1|1]);
}
signed main() {
	n=read(),m=read();
	for(int i=1;i<=n;i++) {
		a[i].l=read(),a[i].r=read();
		a[i].len=a[i].r-a[i].l;
		c[++g]=a[i].l;
		c[++g]=a[i].r;
	}
	sort(c+1,c+g+1);
	for(int i=1;i<=n*2;i++)
		if(!mp[c[i]])
			mp[c[i]]=g++;
	for(int i=1;i<=n;i++)
		a[i].l=mp[a[i].l],a[i].r=mp[a[i].r];
	sort(a+1,a+n+1,cmp);
	while(r<n) {
		while(r<n&&mx[1]<m) {
			r++;
			modify(1,1,g,a[r].l,a[r].r,1);
		}
		if(mx[1]<m)
			continue;
		while(l<=r&&mx[1]>=m) {
			ans=min(ans,a[r].len-a[l].len);
			modify(1,1,g,a[l].l,a[l].r,-1);
			l++;
		}
	}
	if(ans==INF)
		return puts("-1"),0;
	printf("%lld\n",ans);
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...