UOJ上卡掉一个点,COGS上卡掉两个点..弃疗,不改了,反正BZOJ上过啦hhh
先把区间按长度递增排序。然后每次用线段树维护区间最大覆盖次数,用一个指针随便扫扫就行了。
//NOI 2016 D2T1 //by Cydiater //2016.9.18 #pragma GCC optimize("O2") #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <ctime> #include <cmath> #include <iomanip> using namespace std; #define ll long long #define up(i,j,n) for(INT i=j;i<=n;i++) #define down(i,j,n) for(INT i=j;i>=n;i--) #define FILE "interval" #define INT unsigned int ; const INT oo=0x3f3f3f3f; map<INT,INT> lable; inline INT read(){ ,f=; ;ch=getchar();} +ch-';ch=getchar();} return x*f; } INT num[MAXN],N,M,top=,cnt=,check=,x,y,v,ans=oo; struct Query{ INT st,nd,len; }q[MAXN]; struct Tree{ INT maxx,delta; }t[MAXN<<]; namespace solution{ inline bool cmp(Query a,Query b){return a.len<b.len;} inline void downit(INT node){ )return; t[node<<].delta+=t[node].delta;t[node<<|].delta+=t[node].delta; t[node<<].maxx+=t[node].delta;t[node<<|].maxx+=t[node].delta; t[node].delta=; } inline ].maxx,t[node<<|].maxx);} void updata(INT leftt,INT rightt,INT root){ downit(root); if(leftt>y||rightt<x) return; if(leftt>=x&&rightt<=y){ t[root].maxx+=v; t[root].delta+=v; return; } INT mid=(leftt+rightt)>>; updata(leftt,mid,root<<); updata(mid+,rightt,root<<|); reload(root); } void init(){ N=read();M=read(); up(i,,N){ q[i].st=read();q[i].nd=read(); num[++top]=q[i].st;num[++top]=q[i].nd; } sort(num+,num+top+); up(i,,top)if(!lable[num[i]])lable[num[i]]=++cnt; up(i,,N){ q[i].len=q[i].nd-q[i].st; q[i].st=lable[q[i].st]; q[i].nd=lable[q[i].nd]; } sort(q+,q+N+,cmp); } void slove(){ up(i,,N){ ].maxx<M&&check<N){ check++; x=q[check].st;y=q[check].nd;v=; updata(,cnt,); } ].maxx>=M)ans=min(ans,q[check].len-q[i].len); x=q[i].st;y=q[i].nd;v=-; updata(,cnt,); } } void output(){ if(ans==oo)puts("-1"); else cout<<ans<<endl; } } int main(){ //freopen(FILE".in","r",stdin); //freopen(FILE".out","w",stdout); //freopen("input.in","r",stdin); using namespace solution; init(); slove(); output(); ; }