【ZJOI2019】浙江省选

foreverlasting

2019-05-06 15:46:50

Solution

[推销博客](https://foreverlasting1202.github.io/) 半平面交。 说个心酸经历,考场上半平面交板子不会了,然后就没有然后了。 这道题其实的确没有思维含量吧(?)首先第一名显然就是简单的半平面交,然后去掉第一名后,剩下的新出现的第一名就是第二名。然而不能一个个删去,肯定要把所有第一名删去。接着拿第一名们会使哪一段$x$坐标范围的名次$+1$,这个可以二分个位置,然后扫描线一下。当某人在边界上而且最多只被一个人覆盖的话,他的排名就可以上升了。 所以还是挺简单的。 code: ```cpp //2019.5.6 by ljz #include<bits/stdc++.h> using namespace std; #define res register LL #define LL long long #define inf 0x3f3f3f3f3f3f3f #define eps 1e-10 #define RG register inline LL read() { res s=0,ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar(); return s; } inline LL Read() { RG LL s=0; res ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar(); return s; } const LL N=1e5+10; namespace MAIN { LL n,m; struct P{ LL k,id; LL b; P() {} P(res k,RG LL b,res id):k(k),b(b),id(id) {} inline bool operator < (const P &B) const { return k!=B.k?k<B.k:b>B.b; } }a[N]; LL ans[N]; P st[N]; struct A{ LL a; LL b,c; A() {a=b=0,c=1;} A(RG LL x,res y){ if(y<0)x=-x,y=-y; a=x/y,b=int(x%y),c=y; if(b<0)b+=c,a--; } inline bool operator < (const A &x) const { return a==x.a?b*x.c<x.b*c:a<x.a; } inline bool operator <=(const A &x) const { return a==x.a?b*x.c<=x.b*c:a<x.a; } inline LL floor(){ return a; } inline LL ceil(){ return a+(b>0); } }St[N]; inline A cross(const RG P &a,const RG P &b){ return A(b.b-a.b,a.k-b.k); } typedef pair<LL,LL> Pair; #define mp make_pair #define fi first #define se second Pair sT[N<<1]; inline void solve(const res &rnk){ res tot=0,top=0; St[0]=A(0,1); for(res i=1;i<=n;i++) if(ans[a[i].id]==-1&&a[i].k>st[top].k){ while(top&&cross(a[i],st[top]).floor()<St[top].ceil())top--; st[++top]=a[i]; if(top>1)St[top]=cross(st[top-1],a[i]); } St[top+1]=A(inf,1); for(res i=1;i<=n;i++) if(ans[a[i].id]!=-1){ res l=1,r=top,ret=0; while(l<=r){ res mid=(l+r)>>1; if(st[mid].k>=a[i].k||cross(st[mid],a[i])<=St[mid+1])ret=mid,r=mid-1; else l=mid+1; } sT[++tot]=mp(st[ret].k>=a[i].k?0:cross(st[ret],a[i]).floor()+1,1); l=1,r=top,ret=0; while(l<=r){ res mid=(l+r)>>1; if(st[mid].k<=a[i].k||St[mid]<=cross(st[mid],a[i]))ret=mid,l=mid+1; else r=mid-1; } if(st[ret].k>a[i].k)sT[++tot]=mp(cross(st[ret],a[i]).ceil(),-1); } sort(sT+1,sT+tot+1); for(res i=1,j=1,x=0;i<=top;i++){ while(j<=tot&&sT[j].fi<=St[i].ceil())x+=sT[j++].se; if(x==rnk-1)ans[st[i].id]=rnk; while(j<=tot&&sT[j].fi<=St[i+1].floor()){ res p=j; while(p<=tot&&sT[p].fi==sT[j].fi)x+=sT[p++].se; if(x==rnk-1)ans[st[i].id]=rnk; j=p; } } } inline void MAIN(){ n=read(),m=read(); for(res i=1;i<=n;i++){ res k=read(); RG LL b=Read(); a[i]=P(k,b,i),ans[i]=-1; } sort(a+1,a+n+1); for(res i=1;i<=m;i++)solve(i); for(res i=1;i<=n;i++)printf("%lld ",ans[i]); } } int main() { // freopen("graph.in","r",stdin); // freopen("graph.out","w",stdout); MAIN::MAIN(); return 0; } ```