LibreOJ 3047 「ZJOI2019」浙江省选

发表于 | 分类于 | 6

总算是补完 ZJOI2019 了（

首先，排名为 1 的显然是个半平面交问题（把每条直线看做其上方的整个半平面，求交，边界上的就是排名为 1 的）。
实际上也就是求一个下凸壳。
注意 x 是非负整数。

那么考虑排名为 2 的。
显然把排名为 1 的删去之后，排名为 2 的一定也在下凸壳上。
但这只是必要条件，并不充分。因为还应该存在某个 x 使得此处只有一条排名为 1 的直线在其上方。

这个的处理方法是枚举一条排名为 1 的直线，二分出其在凸壳上覆盖的位置，然后扫描线便可得到所有直线的覆盖情况了。

然后排名为 3,4,…,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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m;
int ans[N + 5];
struct frac
{
    long long x,y;
    long long z;
    inline frac(long long a = 0,long long b = 1)
    {
        b < 0 && (a = -a,b = -b);
        z = a / b,x = a % b,y = b;
        x < 0 && (x += y,--z);
    }
    inline long long floor()
    {
        return z;
    }
    inline long long ceil()
    {
        return z + (x > 0);
    }
    inline bool operator<=(const frac &o) const
    {
        return z < o.z || (z == o.z && (x * o.y <= o.x * y));
    }
} inter[N + 5];
struct Linear
{
    long long k,b;
    int id;
    inline Linear(long long x = 0,long long y = 0,int z = 0)
    {
        k = x,b = y,id = z;
    }
    inline bool operator<(const Linear &o) const
    {
        return k < o.k || (k == o.k && b > o.b);
    }
} a[N + 5],s[N + 5];
int top;
inline frac intersection(const Linear &a,const Linear &b)
{
    return frac(b.b - a.b,a.k - b.k);
}
pair<long long,int> t[(N << 1) + 5];
int cnt;
void solve(int k)
{
    top = cnt = 0;
    for(register int i = 1;i <= n;++i)
        if(ans[a[i].id] == -1 && (!top || a[i].k > s[top].k))
        {
            for(;top && a[i].b >= s[top].b;--top);
            for(;top > 1 && intersection(a[i],s[top]).floor() < inter[top].ceil();--top);
            s[++top] = a[i];
            top > 1 && (inter[top] = intersection(s[top - 1],s[top]),1);
        }
    inter[top + 1] = frac(1e18,1);
    for(register int i = 1;i <= n;++i)
        if(~ans[a[i].id])
        {
            int l = 1,r = top,mid,L = 0,R = 0;
            while(l <= r)
                mid = l + r >> 1,
                (s[mid].k >= a[i].k || intersection(s[mid],a[i]) <= inter[mid + 1]) ? (L = mid,r = mid - 1) : (l = mid + 1);
            t[++cnt] = make_pair(s[L].k >= a[i].k ? 0 : intersection(s[L],a[i]).floor() + 1,1);
            l = 1,r = top;
            while(l <= r)
                mid = l + r >> 1,
                (s[mid].k <= a[i].k || inter[mid] <= intersection(s[mid],a[i])) ? (R = mid,l = mid + 1) : (r = mid - 1);
            t[++cnt] = make_pair(s[R].k <= a[i].k ? 1e18 + 1 : intersection(s[R],a[i]).ceil(),-1);
        }
    sort(t + 1,t + cnt + 1);
    for(register int i = 1,j = 1,rk = 0;i <= top;++i)
    {
        for(;j <= cnt && t[j].first <= inter[i].ceil();rk += t[j++].second);
        rk == k - 1 && (ans[s[i].id] = k);
        for(register int x;j <= cnt && t[j].first <= inter[i + 1].floor();j = x)
        {
            for(x = j;x <= cnt && t[x].first == t[j].first;rk += t[x++].second);
            rk == k - 1 && (ans[s[i].id] = k);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m),memset(ans,-1,sizeof ans);
    for(register int i = 1;i <= n;++i)
        scanf("%lld%lld",&a[i].k,&a[i].b),a[i].id = i;
    sort(a + 1,a + n + 1);
    for(register int i = 1;i <= m;++i)
        solve(i);
    for(register int i = 1;i <= n;++i)
        printf("%d%c",ans[i]," \n"[i == n]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment