ARC069D Flags

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 将 个标志放在数轴上。第 个标志可以放置在坐标 或 上。

求出两个标志之间最小距离的最大值。

，时限 。

先二分答案，然后用 判定。

枚举点标志 ，对于另标志 ，按如下规则连边。

  • :

  • :

  • :

  • :

缩点后，若 在同一个联通块内，则无解。

不难用（两颗）线段树优化建边。复杂度为 。

常数大得有点离谱……