M_sea

洛谷5328 [ZJOI2019]浙江省选
LuoguLOJ分析我们把每个人看做一条直线。首先做一遍半平面交(简单版)那么在半平面交上的人都可以拿第一名。接着...
扫描右侧二维码阅读全文
01
2019/06

洛谷5328 [ZJOI2019]浙江省选

Luogu

LOJ

分析

我们把每个人看做一条直线。

首先做一遍半平面交(简单版)那么在半平面交上的人都可以拿第一名。

接着考虑第二名。显然如果一个人想要拿第二名,那么他至少在剩下的人中要能拿到第一名。

那么先跑一遍半平面交,然后得到所有第二名的候选人。

再把所有第一名拿出来,对每个人二分求出一个范围 $[l,r]$ ,满足在这个范围内他是第一名。然后把这个区间覆盖一次。

那么,如果一个点只被覆盖了一次,那么它就可以拿到第二名;如果一个点被覆盖了多于一次,那么它就拿不到第二名。

第三名、第四名、……、第 $m$ 名以此类推,每次做一遍半平面交+二分即可。

另外代码细节非常多,一定要考虑清楚。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct frac { //a+b/c
    ll a,b,c;
    frac(ll x=0,ll y=0) {
        if (y<0) x=-x,y=-y;
        a=x/y,b=x%y,c=y;
        if (b<0) b+=c,--a;
    }
};
bool operator <(frac a,frac b) {
    if (a.a!=b.a) return a.a<b.a;
    else return a.b*b.c<a.c*b.b;
}
bool operator <=(frac a,frac b) {
    if (a.a!=b.a) return a.a<b.a;
    else return a.b*b.c<=a.c*b.b;
}

inline ll floor(frac a) { return a.a; }
inline ll ceil(frac a) { return a.a+(a.b>0); }

int n,m,id[N],ans[N],sta[N],top=0,tot=0;
ll k[N],b[N];
frac p[N];
pair<ll,int> o[N<<1];

inline frac inter(int x,int y) { return frac(b[y]-b[x],k[x]-k[y]); }

inline void solve(int K) {
    top=0,p[0]=frac(0,1);
    for (re int i=1;i<=n;++i) {
        if (ans[id[i]]!=-1) continue;
        if (k[id[i]]>k[sta[top]]) {
            while (top&&floor(inter(id[i],sta[top]))<ceil(p[top])) --top;
            sta[++top]=id[i];
            if (top>1) p[top]=inter(sta[top-1],sta[top]);
        }
    }
    p[top+1]=frac(1e18,1);
    
    tot=0;
    for (re int i=1;i<=n;++i) {
        if (ans[i]==-1) continue;
        int L=1,R=top-1,res=top;
        while (L<=R) {
            int mid=(L+R)>>1;
            if (k[sta[mid]]>=k[i]||inter(sta[mid],i)<=p[mid+1]) res=mid,R=mid-1;
            else L=mid+1;
        }
        o[++tot]=make_pair(k[sta[res]]>=k[i]?0:floor(inter(sta[res],i))+1,1);
        L=2,R=top,res=1;
        while (L<=R) {
            int mid=(L+R)>>1;
            if (k[sta[mid]]<=k[i]||p[mid]<=inter(sta[mid],i)) res=mid,L=mid+1;
            else R=mid-1;
        }
        if (k[sta[res]]>k[i]) o[++tot]=make_pair(ceil(inter(sta[res],i)),-1);
    }

    sort(o+1,o+tot+1);
    for (re int i=1,j=1,s=0;i<=top;++i) {
        while (j<=tot&&o[j].first<=ceil(p[i])) s+=o[j].second,++j;
        if (s<K) ans[sta[i]]=K;
        while (j<=tot&&o[j].first<=floor(p[i+1])) {
            int l=j;
            while (l<=tot&&o[l].first==o[j].first) s+=o[l].second,++l;
            if (s<K) ans[sta[i]]=K;
            j=l;
        }
    }
}

inline int cmp(int x,int y) { return k[x]<k[y]||(k[x]==k[y]&&b[x]>b[y]); }

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) k[i]=read(),b[i]=read(),id[i]=i;
    sort(id+1,id+n+1,cmp);
    memset(ans,-1,sizeof(ans));
    for (re int i=1;i<=m;++i) solve(i);
    for (re int i=1;i<=n;++i) printf("%d ",ans[i]); puts("");
    return 0;
}
最后修改:2019 年 06 月 01 日 10 : 08 AM

4 条评论

  1. smy

    M_sea来写希望吧

    只要3.3k

    1. M_sea
      @smy

      咕咕咕

  2. Siyuan

    M_sea 把浙江省选秒了!

    1. M_sea
      @Siyuan

      明明看了好久才看懂/kk

发表评论