1079. 环城旅行

时间限制 1000 ms
内存限制 128 MB

题目描述

  Matrix67要带他的女友进行一次环城旅行。他选择了一条总长度为L的封闭路线。他所选择的路线上有n个景点。他将从某个景点出发,顺时针开车绕城市一周,再回到出发点。出发前,油箱为空。每个景点内都有一个加油站,第i个景点的加油站提供的油可供车行驶Si的路程。所有加油站可提供的油的总和恰好够汽车行驶一周(即S1+S2+…+Sn=L)。汽车的油箱总能够容下所得到的汽油。临行前的那一天,Matrix67突然意识到,虽然所有加油站的油的总和等于汽车环城一周要消耗的油,但汽车不一定能环城一周,因为有可能还没有到下一个景点,汽油就用光了。显然,是否会发生半路上没油的情况取决于Matrix67选择的出发点。他可不希望和MM的这次浪漫的旅行就这样泡汤了。他知道每个景点离它前一个景点有多远,也知道每个景点的加油站提供的油量。他希望你能帮助他找出,从哪些景点出发可以顺利绕城一周。

输入数据

  第一行为两个正整数,分别代表 $n$ 和 $L$ 。输入数据保证 $n\le 500 000, L\le 100 000 000,$ 并且 $n\le L$ 。
  第二行到第 $n+1$ 行这 $n$ 行数据将按环行道路上顺时针的顺序依次描述各个景点。每行有两个正整数。第 $i+1$ 行为 $Di$ 和 $Si,$ 分别表示第 $i$ 个景点离其前一个景点(即第 $i-1$ 个景点)的距离和这个景点的加油站所提供的油可供汽车行驶的距离。其中 $,D1=0$ 。最后一个(第 $n$ 个)景点与第一个景点之间的距离没有直接给出,但可以根据输入数据计算出来。
  输入数据保证,所有的 $Si$ 之和等于 $L,$ 所有的 $Di$ 之和小于 $L$ 。

输出数据

  一行正整数。输出时,每两个正整数之间都有一个空格,行末无空格。它们表示所有能够作为出发点顺利完成环城旅行的景点。
  当存在多个这样的景点时,请按照升序排列输出他们的序号。
  当不存在这样的景点时,输出-1

样例输入

5 10
0 1
2 2
3 2
2 2
2 3

样例输出

3 4 5

题目信息

未提交
未通过无法查看
未通过无法查看