Problem4369--完美照片

4369: 完美照片

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Status] [Submit] [Creator:]

Description

博士为了更好宣传星系,想拍一张战士的宣传照片。但是博士想拍一张“完美的”照片,“完美的”是指是照片中的女战士和男战士的数量相等。他让N(1≤N≤50000)个战士占成一条直线,每个战士都有各自的坐标,坐标的范围是0到10^9,同时每个战士用0和1来表示性别,0表示是女战士,1表示是男战士。
请帮助博士计算出一个区间,使这个区间能够达到“完美”,并使得区间尽可能大。区间的大小为区间内最右边的战士的坐标减去最左边的战士的坐标。
输入中,每种性别至少有一名战士,没有两个战士的坐标相同。

Input

第一行,一个整数N,表示战士的数量
接下来N行,每行两个整数,分别代表战士i的性别和此战士的坐标

Output

1行,一个整数,最大的区间的大小。

Sample Input Copy

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

Sample Output Copy

11

HINT

【数据规模与约定】:
对于30%的数据,1≤N≤1000
对于50%的数据,1≤N≤10000
对于100%的数据,1≤N≤50000

【样例说明】:

有7个战士,像这样在数轴上。
            1                 1  0  1  0                          1        1
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
其中编号为1(at 11),4(at 12),6(at 13),7(at 22)的这4个战士组成一个“完美”的最大的区间,区间大小为22-11=11个单位长度。
【耗时限制】1000ms 【内存限制】128MB

Source/Category