社区讨论
为什么我要开16倍?
P1712[NOI2016] 区间参与者 4已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lo7xswmq
- 此快照首次捕获于
- 2023/10/27 09:31 2 年前
- 此快照最后确认于
- 2023/10/27 09:31 2 年前
RT,我虽然AC了,按道理来说,我不应该只要开 倍的吗,但是我开了 倍才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 条回复,欢迎继续交流。
正在加载回复...