#P4925. [Lydsy1706月赛]城市规划

    ID: 4030 传统题 1000ms 256MiB 尝试: 341 已通过: 106 难度: 4 上传者: 标签>难度分类普及+/提高-贪心区间合并排序与序列处理差分标记区间修改CF1600本OJ付费获取

[Lydsy1706月赛]城市规划

题目描述

比特镇正在修建新建筑。小 Q 想调整大街上的人行道,使尽可能多的人行道位于建筑物前面,同时让移动距离尽可能小。

大街用一条直线表示,人行道是这条直线上的点。每座建筑物在直线上对应一个闭区间 [li,ri][l_i,r_i]。如果一条人行道的坐标位于某座建筑的区间内,包括两个边界,就认为这条人行道在该建筑物前面。建筑物的区间可以重叠,两条人行道也可以在同一坐标。

为了保持人行道之间的相对距离,小 Q 将所有人行道一起平移。可以向左或向右平移,也可以保持原位。设 ss 为平移后处于至少一座建筑物前面的人行道条数,dd 为平移距离的绝对值。请先最大化 ss,再在所有达到最大 ss 的方案中最小化 dd。

输入格式

第一行包含两个正整数 n,mn,m,分别表示人行道数和建筑数,满足 1≤n≤10 0001\le n\le 10\,000、1≤m≤10001\le m\le 1000。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,分别表示各条人行道的坐标,满足 0≤ai≤1060\le a_i\le 10^6。

接下来 mm 行,第 ii 行包含两个整数 li,ril_i,r_i,表示第 ii 座建筑的左右边界,满足 0≤li<ri≤1060\le l_i<r_i\le 10^6。

输出格式

输出一行两个整数 d,sd,s,依次表示最优平移距离的绝对值及在至少一座建筑物前面的人行道条数。

样例

4 2
1 6 6 1
4 5
3 5
1 2

本OJ付费获取