灰灰的DDL

灰灰的DDL

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

DDL(DeadLine) 结束日期,本题中为上交作业的时间

灰灰很喜欢摸鱼,但他不幸在很卷的濮阳上学。

他的学习生活可以抽象化成一个如下的过程:一个学期一共有\(n\)天,每一天上午上完课之后,老师会布置\(k_i\)​个作业,他们的ddl是\(d_{i,1}​,d_{i,2}​,…,d_{i,k_i}\)​​,一个ddl是\(d\)的作业需要在第\(d\)天的23:59完成,而灰灰为了摸鱼,每天下午只写一项作业,而晚上则要打冰与火练KPS。

灰灰会按照以下方式处理作业,假设当前位于第\(i\)天,老师已经布置且未完成的作业集合为\(S\)。那么灰灰会计算,如果今天下午不做作业也能在不新增作业的前提下在以后完成\(S\)内的所有作业(每天最多完成一个),那么今天就不做作业,否则就做作业,做的作业是ddl离当前最近的。比如当前是第\(2\)天,作业的ddl是\({3,4,5}\),那么今天就可以不做作业,因为不新增作业的情况下之后一天一个就行。但如果作业ddl是\({3,3,4}\)则今天必须做一个ddl为\(3\)的作业,不然第\(3\)天就会有两个当天ddl的作业。而如果作业ddl是\({2,2,2}\),虽然灰灰此时无论如何也无法避免无法上交作业的惨剧,但他还是会做掉其中一个。注意,一个错过ddl的作业会被灰灰永久丢弃掉,后面再也不会做它(反正做了也没啥用)。

显然这个策略有可能造成作业的无法上交,你作为先知,知晓这个学期所有的作业布置时间和ddl,灰灰现在想知道他学期结束的时候有多少个作业会错过ddl,请你帮他一下。

输入格式

第一行一个正整数\(n\)表示学期总共天数。
之后\(n\)行,每行开始输入一个数\(k_i\)​,表示当天新布置的作业数,然后\(k_i\)个整数\(d_{i,1},d_{i,2},…,d_{i,k_i}\),表示每一个作业的ddl。

输出格式

输出一个整数,表示灰灰按照上述策略,期末会有多少个作业错过ddl。

样例

输入

5
2 2 5
1 2
1 5
1 4
0

输出

2

数据规模

对于所有数据,\(1 \leqslant n \leqslant 10^5, 1 \leqslant \sum_{i=1}^n k_i \leqslant 2 \times 10^5, i \leqslant d_{i,j} \leqslant n\)

AKIOI Round #1

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-08-08 08:30
结束于
2024-08-08 12:30
持续时间
4.0 小时
主持人
参赛人数
2