ACM-ICPC-OJ训练营

问题 E: 水群大王(模拟)

时间限制: 1 Sec 内存限制: 256 MB
提交: 0 解决: 14
[提交][状态][讨论版][命题人:]

题目描述

DH想成为水群大王，于是他向HYF进行学习，开始疯狂水群，某天，他加入了一个群。
这个群有n个人，总共发了m条消息。
每条消息由一个人发出来的，消息分为水和不水。
还有两个参数a,b。
如果在某一条消息，它以及它之前的a-1条消息（共a条消息）都是在水（不管是不是同一个人发的），那么发这条消息的人就会受到奖励。
如果一个人，在任意一条消息之前，他发的最后b条消息（包括这条）都是在水，那么这个人也会受到奖励
现在DH想要知道，有哪些群友会受到奖励。

输入描述

第一行，四个正整数n,m,a,b(2≤n,m≤3e5,2≤a,b≤m)
后面m行，每行两个整数pi,ti(1≤pi≤n,0≤ti≤1),表示一条消息。
pi表示第pi个人发消息的，ti=1表示这条消息是在水，ti=0表示这条消息不是在水。

输出描述

第一行输出一个数x，表示有x位群友受到奖励
第二行输出x个数，从小到大排列，输出所有受到奖励的群友的编号
如果没有群友受到奖励，只输出0

样例输入

样例输出

3
2 3 4

提示

样例说明：

[1,3]发的消息都是1，所以标号为3的人会受到奖励

[2,4]发的消息都是1，所以标号为4的人会受到奖励

[7,9]发的消息都是1，所以标号为2的人会受到奖励

第1,6,7条消息都是1发的，但是第6条消息不是水的，没有两条连续的水消息，所以标号1的人不会收到奖励

输入：

2 3 2 2

1 0

2 0

1 0

输出：

0

[提交][状态]