今年NOI也有水题好开心啊
离散化，按区间长度排序
枚举最长区间，用线段树维护当前所有区间覆盖的点，那么只要有至少一个点的权值大于等于\(m\)即可，也就是整个区间最值
显然枚举最长区间时最短区间是单增的。用单调队列即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// <4653.cpp> - Wed Aug 3 22:16:21 2016 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=500010; const int INF=2e9; struct num{ int x,p; bool r; num(){} num(int a,int b,bool c){x=a,p=b,r=c;} bool operator <(const num b) const{return x<b.x;} }a[MAXN<<1]; struct noob{ int l,r,len; bool operator <(const noob b) const{return len<b.len;} }d[MAXN]; int n,pos,val[MAXN<<3],lazy[MAXN<<3]; void add(int l,int r,int x,int p,int L=1,int R=pos){ if(l==L&&r==R){ val[p]+=x; lazy[p]+=x; return; } int M=L+R>>1; if(l<=M)add(l,min(M,r),x,p<<1,L,M); if(M+1<=r)add(max(l,M+1),r,x,p<<1|1,M+1,R); val[p]=max(val[p<<1],val[p<<1|1])+lazy[p]; } int main(){ n=gi();int m=gi(),tot=0; for(int i=1;i<=n;i++){ a[++tot]=num(gi(),i,0); a[++tot]=num(gi(),i,1); } sort(a+1,a+tot+1); pos=0; for(int i=1;i<=tot;i++){ if(i==1||a[i].x!=a[i-1].x)a[++pos]=a[i]; if(a[i].r)d[a[i].p].r=pos; else d[a[i].p].l=pos; } for(int i=1;i<=n;i++)d[i].len=a[d[i].r].x-a[d[i].l].x; sort(d+1,d+n+1); int ans=INF,ps=1; for(int i=1;i<=n;i++){ add(d[i].l,d[i].r,1,1); for(;val[1]>=m;ps++){ ans=min(ans,d[i].len-d[ps].len); add(d[ps].l,d[ps].r,-1,1); } } printf("%d",ans==INF?-1:ans); return 0; } |
说点什么