3278. 小明种苹果(续)

小明在他的果园里种了一些苹果树,这些苹果树排列成一个圆。

为了保证苹果的品质,在种植过程中要进行疏果操作。

为了更及时地完成疏果操作,小明会不时地检查每棵树的状态,根据需要进行疏果。

检查时,如果发现可能有苹果从树上掉落,小明会重新统计树上的苹果个数(然后根据之前的记录就可以判断是否有苹果掉落了)。

在全部操作结束后,请帮助小明统计相关的信息。

输入格式

第 $1$ 行包含一个正整数 $N$,表示苹果树的棵数。

第 $1+i$ 行( $1 \le i \le N$),每行的格式为 $m_i,a_{i1},a_{i2},…,a_{im_i} $。其中,第一个正整数 $m_i$ 表示本行后面的整数个数。后续的 $m_i$ 个整数表示小明对第 $i$ 棵苹果树的操作记录。若 $a_{ij} ( 1 ≤ j \le m_i)$ 为正整数,则表示小明进行了重新统计该棵树上的苹果个数的操作,统计的苹果个数为 $a_{ij}$;若为零或负整数,则表示一次疏果操作,去掉的苹果个数是 $|a_{ij}|$。

输入保证一定是正确的,满足:

  1. $a_{i1} > 0$,即对于每棵树的记录,第一个操作一定是统计苹果个数(初始状态,此时不用判断是否有苹果掉落);
  2. 每次疏果操作保证操作后树上的苹果个数仍为正。

输出格式

输出只有一行,包含三个整数 $T、D、E$。其中,

  • $T$ 为全部疏果操作结束后所有苹果树上剩下的苹果总数(假设每棵苹果树在最后一次统计苹果个数操作后苹果不会因为疏果以外的原因减少);
  • $D$ 为发生苹果掉落的苹果树的棵数;
  • $E$ 为相邻连续三棵树发生苹果掉落情况的组数。

对于第三个统计量的解释:$N$ 棵苹果树 $A_1,A_2,…,A_N$ 排列成一个圆,那么 $A_1$ 与 $A_2$ 相邻,$A_2$ 与 $A_3$ 相邻,......,$A_{N-1}$ 与 $A_N$ 相邻,$A_N$ 与 $A_1$ 相邻。如果 $A_{i-1},A_i,A_{i+1}$ 这三棵树都发生了苹果掉落的情况,则记为一组。形式化的,有

$$E = | \{A_i|Drop(Pred(A_i)) \land Drop(A_i) \land Drop(Succ(A_i))\} |$$

其中,$Drop(A_i)$ 表示苹果树 $A_i$ 是否发生苹果掉落的情况,$Pred(A_i)$ 表示 $A_i$ 的前一棵树 $A_{i-1}$ (如果 $i>1$)或者 $A_N$(如果 $i= 1$),$Succ(A_i)$ 表示 $A_i$ 的后一棵树 $A_{i+1}$(如果 $i<N$)或者 $A_1$(如果 $i = N$)。

数据范围

QQ截图20210223110946.png

$m_i \le 1000$,对于所有 $1 \le i \le N$。
$|a_{ij}| \le 10^6$,对于所有 $1 \le i \le N,1 \le j \le m_i$。

输入样例1:

4
4 74 -7 -12 -5
5 73 -8 -6 59 -4
5 76 -5 -10 60 -2
5 80 -6 -15 59 0

输出样例1:

222 1 0

样例1解释

全部操作结束后,第 $1$ 棵树上剩下的苹果个数为 $74-7-12-5 = 50$,第 $2$ 棵为 $59-4 =55$,第 $3$ 棵为 $60-2= 58$,第 $4$ 棵为 $59-0 = 59$。

因此 $T = 50+55+58+59 = 222$。

其中,第 $3$ 棵树在第 $2$ 次统计之前剩下的苹果个数为 $76-5-10 =61 > 60$,因此发生了苹果掉落的情况。

可以检验其他的树没有这种情况,因此 $D=1$。

没有连续三棵树都发生苹果掉落的情况,因此 $E=0$。

输入样例2:

5
4 10 0 9 0
4 10 -2 7 0
2 10 0
4 10 -3 5 0
4 10 -1 8 0

输出样例2:

39 4 2

样例2解释

第 $1、2、4、5$ 棵树发生了苹果掉落的情况,因此 $D=4$。

其中,连续三棵树都发生苹果掉落情况的有 $(5,1,2)$ 和 $(4,5,1)$,因此 $E=2$。