Codeforces GYM 101147F. Bishops Alliance

正文索引 [隐藏]

传送门:http://codeforces.com/gym/101147/problem/F

题目翻译

一些棋子分别在(\left ( X_{i},Y_{i} \right )),有属性(P_{i}),如果一条对角线上的棋子之间两两满足(\left | X_i – Y_i \right | \geqslant P_i^2+P_j^2+C-1),即可形成一条防守线。求最长防守线长度。

题解

按照对角线,把所有点分类。
新的(i),如果对于一个已经符合的团体,最右边的点(j),有(X_i > X_j),(X_i – P_i^2\geqslant X_j + P_j^2 + C -1),那么点(i)能加入这个点(j),所在的集合。
令(A_i =X_i – P_i^2 ),(B_i=X_i + P_i^2 + C -1)且(A_i<B_i)。
所以对于同一条对角线上面的点,按照(X)排序,单调队列维护(B_i)即可。

代码