#P1973. [NOI2011] NOI 嘉年华
[NOI2011] NOI 嘉年华
题目描述
NOI2011 在吉林大学开始啦!为了迎接来自全国各地最优秀的信息学选手,吉林大学决定举办两场盛大的 NOI 嘉年华活动,分在两个不同的地点举办。每个嘉年华可能包含很多个活动,而每个活动只能在一个嘉年华中举办。
现在嘉年华活动的组织者小安一共收到了 个活动的举办申请,其中第 个活动的起始时间为 ,活动的持续时间为 。这些活动都可以安排到任意一个嘉年华的会场,也可以不安排。
小安通过广泛的调查发现,如果某个时刻,两个嘉年华会场同时有活动在进行(不包括活动的开始瞬间和结束瞬间),那么有的选手就会纠结于到底去哪个会场,从而变得不开心。所以,为了避免这样不开心的事情发生,小安要求不能有两个活动在两个会场同时进行(同一会场内的活动可以任意进行)。
另外,可以想象,如果某一个嘉年华会场的活动太少,那么这个嘉年华的吸引力就会不足,容易导致场面冷清。所以小安希望通过合理的安排,使得活动相对较少的嘉年华的活动数量最大。
此外,有一些活动非常有意义,小安希望能举办,他希望知道,如果第 个活动必须举办(可以安排在两场嘉年华中的任何一个),活动相对较少的嘉年华的活动数量的最大值。
输入格式
输入的第一行包含一个整数 ,表示申请的活动个数。
接下来 行描述所有活动,其中第 行包含两个整数 ,表示第 个活动从时刻 开始,持续 的时间。
输出格式
输出的第一行包含一个整数,表示在没有任何限制的情况下,活动较少的嘉年华的活动数的最大值。
接下来 行每行一个整数,其中第 行的整数表示在必须选择第 个活动的前提下,活动较少的嘉年华的活动数的最大值。
提示
样例解释
在没有任何限制的情况下,最优安排可以在一个嘉年华安排活动 ,而在另一个嘉年华安排活动 ,活动 不安排。
对于 的数据,。
对于 的数据,。
对于 的数据,,,。
如果输出格式不正确(比如输出不足 行),得 分;
如果输出文件第一行不正确,而且后 行至少有一行不正确,得 分;
如果输出文件第一行正确,但后 行至少有一行不正确,得 分;
如果输出文件第一行不正确,但后 行均正确,得 分;
如果输出文件中的 行均正确,得 分。