总算是补完 ZJOI2019 了（
首先，排名为 \(1\) 的显然是个半平面交问题（把每条直线看做其上方的整个半平面，求交，边界上的就是排名为 \(1\) 的）。
实际上也就是求一个下凸壳。
注意 \(x\) 是非负整数。
那么考虑排名为 \(2\) 的。
显然把排名为 \(1\) 的删去之后，排名为 \(2\) 的一定也在下凸壳上。
但这只是必要条件，并不充分。因为还应该存在某个 \(x\) 使得此处只有一条排名为 \(1\) 的直线在其上方。
这个的处理方法是枚举一条排名为 \(1\) 的直线，二分出其在凸壳上覆盖的位置，然后扫描线便可得到所有直线的覆盖情况了。
然后排名为 \(3,4,\dots,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
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]);
}