Description

Input

第一行为两个空格隔开的正整数n, m，表示旅行的城市数与旅行所花的月数。接下来n行，其中第 i行包含两个空格隔开的整数Ai和Bi，Ai表示他第i个去的城市编号。Bi为0或1;如果Bi=0则表示城市Ai没有小L想去的景点，如果Bi=1则表示城市Ai有小L想去的景点，
Ai两两不同且有1<=Ai<=N,即{Ai}为1,2….N的一个排列。
例如{2,1,3,4…N}
N<=500000,M<=200000

Output

t仅包括一行，包含m个空格隔开的正整数X1,X2…Xm，t仅包括一行，包含m个空格隔开的正整数X1,X2…Xm，为给小L安排的旅行计划对应的路线。为给小L安排的旅行计划对应的路线。

Sample Input

8 3

2 0

3 1

4 1

1 0

5 0

6 1

7 1

8 0

Sample Output

1 6 8

HINT

第1个月得到2点快乐值与2点疲劳值，第2个月得到1点快乐值与1点疲劳值，第3 个月得到1点快乐值与1点疲劳值。3个月中疲劳值与快乐值差的最大值为0，达到所有方 案最小值。

可行方案有：

1 6 8

3 6 8

3 1 8

其中1 6 8字典序最小。

感谢两位的题解http://www.cnblogs.com/lazycal/archive/2013/07/29/3221342.html和http://cxjyxx.me/?p=329

基本上就是他们说的了，本人愚笨，两天才刷掉它

我就随便讲一下
对每一个s[i]做一个单调队列
在单调队列里维护a[i]单调递增
当ans为0时
每次把可以作为解的点加入单调队列，把a[i]比他小的都删掉，然后取队头
当ans不为0时
如果n-m+1可以做现在的解，把n-m+1这个点加进单调队列，操作一样
为什么可以这样做，我认为是因为入队的顺序本来是按从近到远的顺序，而且都可以作为现在的解，如果a[i]比a[j]大，j在i后面，那肯定就把i删除了

var
s,sum,sum2,c:array[..]of longint;
first,tail:array[-..]of longint;
next,pre,num:array[..]of longint;
n,m,ans,tot,l:longint;

function get(l,m:longint):longint;
begin
if sum[l]= then
if sum2[l]>=m then exit()
else exit()
else
begin
get:=abs(sum[l])div m;
if abs(sum[l])mod m> then inc(get);
end;
end;

procedure insert(x:longint);
var
i:longint;
begin
if get(x+,m-)>ans then exit;
inc(tot);
num[tot]:=x;
if first[sum[x+]]= then
begin
first[sum[x+]]:=tot;
tail[sum[x+]]:=tot;
exit;
end;
i:=tail[sum[x+]];
while (i<>)and((c[num[i]]>c[x])or(num[i]<l)) do
begin
if pre[i]= then
begin
i:=;
break;
end;
i:=pre[i];
end;
if i= then
begin
first[sum[x+]]:=tot;
tail[sum[x+]]:=tot;
exit;
end;
pre[tot]:=i;
next[i]:=tot;
tail[sum[x+]]:=tot;
end;

procedure work2;
var
i,k:longint;
begin
l:=;
k:=;
while m> do
begin
while sum2[k]>=m- do
begin
if sum[k+]= then insert(k);
inc(k);
end;
while num[first[]]<l do
first[]:=next[first[]];
pre[first[]]:=;
write(c[num[first[]]],' ');
l:=num[first[]]+;
dec(m);
end;
write(c[n]);
halt;
end;

procedure init;
var
i:longint;
begin
read(n,m);
for i:= to n do
begin
read(c[i],s[i]);
if s[i]= then s[i]:=-;
end;
for i:=n downto do
begin
sum[i]:=sum[i+]+s[i];
sum2[i]:=sum2[i+];
if sum[i]= then inc(sum2[i]);
end;
ans:=get(,m);
if ans= then work2;
for i:= to n-m do
insert(i);
end;

procedure work;
var
i,j,min,sl,sr:longint;
begin
l:=;
while m> do
begin
insert(n-m+);
sl:=sum[l]-ans;
sr:=ans+sum[l];
j:=;
min:=;
for i:=sl to sr do
begin
while (first[i]<>)and((num[first[i]]ans)) do
first[i]:=next[first[i]];
pre[first[i]]:=;
if first[i]<> then
if c[num[first[i]]]<min then
begin
min:=c[num[first[i]]];
j:=num[first[i]];
end;
end;
write(min,' ');
l:=j+;
dec(m);
end;
write(c[n]);
end;

begin
init;
work;
end.