【ZJOI2019】浙江省选

推销博客

半平面交。

说个心酸经历，考场上半平面交板子不会了，然后就没有然后了。

这道题其实的确没有思维含量吧（？）首先第一名显然就是简单的半平面交，然后去掉第一名后，剩下的新出现的第一名就是第二名。然而不能一个个删去，肯定要把所有第一名删去。接着拿第一名们会使哪一段x坐标范围的名次+1，这个可以二分个位置，然后扫描线一下。当某人在边界上而且最多只被一个人覆盖的话，他的排名就可以上升了。

所以还是挺简单的。

code:

//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;
}